题目
超市里有N件商品，每个商品都有利润pi和过期时间di,每天只能卖一件商品，过期商品（即当天di<=0）不能再卖。
求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。
输入格式
输入包含多组测试用例。
每组测试用例，以输入整数N开始，接下里输入N对pi和di，分别代表第i件商品的利润和过期时间。
在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。
输出格式
对于每组产品，输出一个该组的最大收益值。
每个结果占一行。
数据范围
0≤N≤10000, 1≤pi,di≤10000
输入样例：
4
50 2 10 1 20 2 30 1
7
20 1 2 1 10 3 100 2 8 2 5 20 50 10
输出样例：
80
185
分析
这个题目，我们可以运用贪心的思想来解决，对于价值高的我们能放的都放进去。这个题可以有多种解法，我这里只简要介绍两种：优先队列解法和并查集解法第一种解法：按照天数来从小到大排序，用小顶堆优先队列来维护，当优先队列的元素个数小于当前遍历到的i商品的过期天数少数，就将它放入，如果元素个数等于现在的天数时，如果现在的商品的价值大于优先队列中队顶元素时，那么我们就将队顶元素出队，将该商品的加入队列，我们知道，因为去掉队顶以后队里元素是小于过期天数的，因此这个商品可以加入，贪心方案正确。
代码：
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <limits.h>
using namespace std;
const int N=1e4+5;
priority_queue<int,vector<int>,greater<int> > q;
int n;
pair<int,int> p[N];
int main()
{
while(cin>>n){
int maxd=INT_MAX;
for(int i=0;i<n;i++){
cin>>p[i].second>>p[i].first;
}
sort(p,p+n);
for(int i=0;i<n;i++){
if(q.size()<p[i].first) q.push(p[i].second);
else {
if(p[i].second>q.top()){
q.pop();
q.push(p[i].second);
}
}
}
int ans=0;
while(!q.empty()){
ans+=q.top();
q.pop();
}
cout<<ans<<endl;
}
return 0;
}
第二种做法，将商品按价值排序，每次将价值最多的试图加入他过期前某一天中，这个某一天用并查集来维护，i点代表第i天，即用并查集来标记这个当前点或者前面哪个点是空的。如果是零，那么就是当前点前面没有为空的点，代表全部已经装满，初始化的时候将每个点指向自己，代表前面第一个为空的点是自己，因为我们是从最大价值枚举的，因此后面不能装下的一定不是最优的。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e4+5,M=10000;
int pre[N];
int find(int x){
if(pre[x]!=x) pre[x]=find(pre[x]);
return pre[x];
}
int n;
pair<int,int> p[N];
int main()
{
ios::sync_with_stdio(false);
while(cin>>n){
for(int i=0;i<n;i++){
cin>>p[i].first>>p[i].second;
}
sort(p,p+n);
int ans=0;
for(int i=0;i<=M;i++) pre[i]=i;
for(int i=n-1;~i;i--){
int v=p[i].first,w=p[i].second;
int f=find(w);
if(f>0){
ans+=v;
pre[f]=f-1;
}
}
cout<<ans<<endl;
}
return 0;
}
