牛券Cow Coupons

向右看齐 2024-04-20 10:27 50阅读 0赞

##  ##

USACO12FEB

> 久违的奶牛题。

### 题意： ###

> FJ准备买一些新奶牛，市场上有 $ N $ 头奶牛 $ (1 \\leq N \\leq 50000) $ ，第i头奶牛价格为 $ P\_i (1 \\leq P\_i \\leq 10^9) $ 。FJ有K张优惠券，使用优惠券购买第i头奶牛时价格会降为 $ C\_i(1\\leq C\_i \\leq P\_i) $ ，每头奶牛只能使用一次优惠券。FJ想知道花不超过 $ M(1 \\leq M \\leq 10^\{14\}) $ 的钱最多可以买多少奶牛？

### 解法： ###

> 在ZR时摸鱼王讲的一道贪心题。  
> 但这道题并不是一道裸贪心，直接对 $ C $ 排序，取前 $ k $ 个数并不完全对，具体为什么自己想想。  
> 正确的做法依旧是贪心，不过是可以反悔的贪心。  
> 我们优先处理使用优惠券之后最便宜的几头牛，然后选择剩下的牛中不用券最便宜的，之后判断要不要将用过的一张券转用给一头新的牛。  
> 具体做法就是开一个大根堆，每次维护 $ price\_i - cost\_i $ 就可以了。

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; #define LL long long #define N 50010 LL n,k,m; struct cow { LL price,cost; } node[N]; inline bool cmp1(cow a,cow b) { return a.cost < b.cost; } inline bool cmp2(cow a,cow b) { return a.price < b.price; } priority_queue<LL,vector<LL>,greater<LL> > q; int main() { scanf("%lld%lld%lld",&n,&k,&m); for(int i = 1 ; i <= n ; i++) scanf("%lld%lld",&node[i].price,&node[i].cost); sort(node + 1,node + n + 1,cmp1); LL sum = 0; for(int i = 1 ; i <= k ; i++) { sum += node[i].cost; if(sum > m) { printf("%d \n",i - 1); //system("pause"); return 0; } q.push(node[i].price - node[i].cost); } sort(node + k + 1,node + n + 1,cmp2); for(int i = k + 1 ; i <= n ; i++) { int u = node[i].price - node[i].cost; if(u > q.top()) { sum += q.top(); q.pop(); q.push(u); sum += node[i].cost; } else sum += node[i].price; if(sum > m) { printf("%d \n",i - 1); //system("pause"); return 0; } } printf("%lld \n",n); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11402679.html