BZOJ2590 [Usaco2012 Feb]Cow Coupons

好吧。。。想了半天想错了。。。虽然知道是贪心。。。

我们每次找没有被买的两种价格最小的牛，比较a = 当前差价最大的 + 当前优惠券价格最小的牛与b = 当前非优惠券价格最小的牛

所以。。。我们要

先维护两个小根堆，分别表示用优惠券买的牛的价格和不用优惠券买的牛的价格

还有个叫Recover的大根堆，表示当前几个用优惠券的那几头牛的差价（差价定义为非优惠价格与优惠价格的差值）

a与b哪个小就买哪个。。。

 /**************************************************************

     Problem: 2590

     User: rausen

     Language: C++

     Result: Accepted

     Time:140 ms

     Memory:3332 kb

 ****************************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <queue>

 using namespace std;

 typedef long long ll;

 const int N = ;

 struct data{

     int w, v;

     data(void){}

     data(int x, int y) : w(x), v(y) {}

 };

 inline bool operator < (const data a, const data b){

     return a.v > b.v;

 }

 int cnt, n, k;

 int p[N], c[N];

 bool vis[N];

 ll m;

 priority_queue <data> h, H;

 priority_queue <ll, vector<ll>, greater<ll> > Re;

 inline int read(){

     int x = ;

     char ch = getchar();

     while (ch < '' || ch > '')

         ch = getchar();

     while (ch >= '' && ch <= ''){

         x = x *  + ch - '';

         ch = getchar();

     }

     return x;

 }

 int main(){

     int i;

     ll cost;

     data T;

     n = read(), k = read();

     scanf("%lld", &m);

     for (i = ; i <= n; ++i){

         p[i] = read(), c[i] = read();

         h.push(data(i, c[i]));

         H.push(data(i, p[i]));

     }

     while (!Re.empty()) Re.pop();

     for (i = ; i <= k; ++i)

         Re.push();

     while (m >  && cnt < n){

         while (vis[h.top().w])

             h.pop();

         while (vis[H.top().w])

             H.pop();

         if (Re.top() + h.top().v < H.top().v){

             T = h.top(), cost = Re.top() + T.v;

             if (m < cost) break;

             m -= cost;

             Re.pop();

             Re.push(p[T.w] - c[T.w]);

             vis[T.w] = ;

         }else{

             T = H.top(), cost = T.v;

             if (m < cost) break;

             m -= cost;

             vis[T.w] = ;

         }

         ++cnt;

     }

     printf("%d\n", cnt);

     return ;

 }