Supermarket

题意：

共有n个物品，每个物品有对应的价值，和过期日期，到了过期时间以后这个物品就不能再买了，问可以得到的最大收益是多少？

这道题跟教练跟我们出的贪心杂题中的[建筑抢修]一题比较像。

那道题给了你修筑一个建筑的时间，和截至日期，问最多能修多少建筑。

对于这道题，我们想要让修筑的建筑数量最大化，那么肯定让截止日期快的先修，所以按照截止日期的快慢排序。接着用一个大根堆来维护建筑的，如果一个建筑可以被修，那么就直接修筑，否则比较堆顶元素与当前建筑的修筑时间，看谁更优就到堆中。

回到原题，唯一与刚刚那道题有差异的是，题目给出的不再是修筑建筑的时间，而是一个物品的价值，而且最后求的是收益最大。但我们可以在题目中读出隐藏的条件，购买一个物品的时间是1。所以这道题只不过是在刚刚那道题的基础上为每个建筑增添了一个价格（美观值）

那么我们也可以用类似的方式解决这道题，要使建筑收益最大，那么肯定的一个贪心策略是选的能物品越多越好，所以按照过期时间的快慢来排序，其次保证其中的物品价值是所能选出来的最多的，那么怎么保证选出的几个物品的价值一定是最优的呢？根据上一题的套路，用一个大根堆来维护每个物品的值，如果当前物品已经过期，那么我们可以通过堆来进行后悔，将当前物品与堆顶物品进行比较，若当前物品优于堆顶物品，则将堆顶元素，当前物品。否则将当前物品不入堆中。

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=10000 + 5;
int n,ans;
struct node{
    int p,d;
    bool operator < (const node &v) const{
        return p>v.p;
    }
}s[MAX_N];
bool cmp(node a,node b){
    return a.d<b.d;
}
priority_queue<node> q;
int main(){
    while(scanf("%d",&n)!=EOF){//注意该题有多组输入数据
        ans=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&s[i].p,&s[i].d);
        }
        sort(s+1,s+1+n,cmp);//对d[i]进行排序
        for(int i=1;i<=n;i++){//堆的后悔操作，这里用了一个技巧，先将物品push进堆中，然后比较当前堆的元素个数（时间）是否大于过期时间，若大于，当前元素个数（时间）等于d[i]+1，因为我们是用大根堆维护的p[i]，所以直接pop掉堆顶，如果p[i]<之前堆顶，则push后堆顶不变，若p[i]>之前堆顶，则push后，当前物品成为堆顶，在pop掉。相当于这个物品没有push进堆中。
            q.push(s[i]);
            if(q.size()>s[i].d) q.pop();
        }
        while(q.size()){
            ans+=q.top().p;
            q.pop();
        }
        printf("%d\n",ans);
    }
    return 0;
}