首页 > 代码库 > BZOJ2590 [Usaco2012 Feb]Cow Coupons
BZOJ2590 [Usaco2012 Feb]Cow Coupons
好吧。。。想了半天想错了。。。虽然知道是贪心。。。
我们每次找没有被买的两种价格最小的牛，比较a = 当前差价最大的 + 当前优惠券价格最小的牛与b = 当前非优惠券价格最小的牛
所以。。。我们要
先维护两个小根堆，分别表示用优惠券买的牛的价格和不用优惠券买的牛的价格
还有个叫Recover的大根堆，表示当前几个用优惠券的那几头牛的差价（差价定义为非优惠价格与优惠价格的差值）
a与b哪个小就买哪个。。。
1 /************************************************************** 2 Problem: 2590 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:140 ms 7 Memory:3332 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 #include <queue>13 14 using namespace std;15 typedef long long ll;16 const int N = 50005;17 struct data{18 int w, v;19 data(void){}20 data(int x, int y) : w(x), v(y) {}21 };22 inline bool operator < (const data a, const data b){23 return a.v > b.v;24 }25 int cnt, n, k;26 int p[N], c[N];27 bool vis[N];28 ll m;29 priority_queue <data> h, H;30 priority_queue <ll, vector<ll>, greater<ll> > Re;31 32 inline int read(){33 int x = 0;34 char ch = getchar();35 while (ch < ‘0‘ || ch > ‘9‘)36 ch = getchar();37 while (ch >= ‘0‘ && ch <= ‘9‘){38 x = x * 10 + ch - ‘0‘;39 ch = getchar();40 }41 return x;42 }43 44 int main(){45 int i;46 ll cost;47 data T;48 n = read(), k = read();49 scanf("%lld", &m);50 for (i = 1; i <= n; ++i){51 p[i] = read(), c[i] = read();52 h.push(data(i, c[i]));53 H.push(data(i, p[i]));54 }55 while (!Re.empty()) Re.pop();56 for (i = 1; i <= k; ++i)57 Re.push(0);58 while (m > 0 && cnt < n){59 while (vis[h.top().w])60 h.pop();61 while (vis[H.top().w])62 H.pop();63 if (Re.top() + h.top().v < H.top().v){64 T = h.top(), cost = Re.top() + T.v;65 if (m < cost) break;66 m -= cost;67 Re.pop();68 Re.push(p[T.w] - c[T.w]);69 vis[T.w] = 1;70 }else{71 T = H.top(), cost = T.v;72 if (m < cost) break;73 m -= cost;74 vis[T.w] = 1;75 }76 ++cnt;77 }78 printf("%d\n", cnt);79 return 0;80 }
BZOJ2590 [Usaco2012 Feb]Cow Coupons
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。