BZOJ2590 [Usaco2012 Feb] Cow Coupons

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
    int num, id;
};
bool operator < (node x, node y) 
{
    return x.num > y.num;
}
priority_queue<node> q1, q2; //重载运算符后成为小根堆 
priority_queue<int, vector<int>, greater<int> > q3;
//定义一个小根堆 
int N, K, ans;
long long M;
int use[150001], p[150001], q[150001];
int main() 
{
    scanf("%d %d %lld", &N, &K, &M);
    //N个物品，k张优惠卷,M元钱 
    for (int i = 1; i <= N; i++) 
    {
        scanf("%d %d", &p[i], &q[i]);
        q1.push((node){p[i], i});//放原价 
        q2.push((node){q[i], i});//放优惠价 
    }
    for (int i = 1; i <= K; i++) 
         q3.push(0);//一开始有k张优惠券,价格为0 
    for (; M > 0 && ans < N; ) 
    {
        while (use[q1.top().id]) 
             q1.pop();
        while (use[q2.top().id]) 
             q2.pop();
        if (q1.top().num <= q2.top().num + q3.top()) 
        {//q1这个堆中放的是如果直接买的话，最便宜的
         //q2放的是如果使用优惠券的话，最便宜的
         //对于优惠券我们可以认为开始价格为0，如果如果要赎回的话，自然也是赎回代价最小的 
            node x = q1.top();
            M -= x.num;
            if (M < 0) break;
            use[x.id] = 1;
            q1.pop();
            ans++;
        }
        else {//花券买
            node x = q2.top();
            M -= x.num + q3.top();
            if (M < 0) break;
            use[x.id] = 1;
            q3.pop();
            q3.push(p[x.id] - q[x.id]);
            //新放入这个物品可撤回的优惠券
            q2.pop();
            ans++;
        }
    }
    printf("%d", ans);
}