Supermarket
题目描述
有一个商店有许多批货，每一批货又有N(0<=N<=(10^4))个商品,同时每一样商品都有收益Pi ,和过期时间Di (1<=Pi,Di<=(10^9))，一旦超过了过期时间，商品就不能再卖。
你要做的就是求出每批货最多能得到多少收益。
输入输出格式
输入格式
多组数据，每组先给出一个整数N，表示这批货的商品个数。
然后有N对数，每对数有两个用空格隔开的正整数 Pi,Di ,表示第i个商品的收益和过期时间。相邻两对数之间用空格隔开。
输入以一个文件终止符结束，并且保证所有输入数据正确。
输出格式
对于每组数据，输出一行一个整数表示该批货物能卖出的最大价格。
感谢@Rye_Catcher 提供的翻译
题目描述
输入输出样例
输入样例#1：
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
输出样例#1：
80
185
题解
首先我们应该可以很快想到一个贪心，即按照过期时间从小到大排序，因为一个物品的过期时间越长，它能为其他商品做出的贡献就越多，即更多的商品可以在它之前卖出，这就是正解的第一步
题目要求每天只能卖一个物品，我们为了保证价值最大，一定每天都会卖出物品，即n天一定卖了n件商品，那么我们再想是不是在相同的条件下卖出价值更大的物品更优，有些人可能就会这么想，按照日期为第一关键字从小到大，价值为第二关键字从大到小排序，然后直接一边扫过去
但是这种错误的方法也为我们提供了思路，我们可不可以把价值都存在一个容器里，且这个容器是有序的，方便我们随时更新，没错，就是优先队列。
我们可以建一个小根堆，那么堆顶的元素一定是最小的。而堆内元素的个数size，代表至少已经卖了size间物品即至少已经卖了size天，那么当我们扫到另一个物品时，分三种情况：
如果它的过期天数已经小于size，就代表这件物品在卖了size件物品前就已经过期了，那我们就不用管它.
如果它的过期天数等于size，我们就让它与堆顶元素比较，看谁更优，将更优的那个插入堆中
如果它的过期天数大于size，直接插入堆中
扫完之后堆中的元素之和就是最后的答案
Code
#include<bits/stdc++.h>
#define in(i) (i=read())
using namespace std;
int read()
{
int ans=0,f=1;
char i=getchar();
while(i<'0' || i>'9'){
if(i=='-') f=-1;
i=getchar();
}
while(i>='0' && i<='9'){
ans=(ans<<1)+(ans<<3)+i-'0';
i=getchar();
}
return ans*f;
}
int n;
struct node{
int v,p;
}a[10010];
priority_queue< int,vector<int>,greater<int> >q;
bool cmp(node a,node b){
if(a.p==b.p) return a.v>b.v;
return a.p<b.p;
}
int main()
{
while(cin>>n){
int ans=0;
for(int i=1;i<=n;i++){
in(a[i].v);in(a[i].p);
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
if(a[i].p==q.size()){
int x=q.top();
if(a[i].v>x){
q.pop();
q.push(a[i].v);
}
}
else if(a[i].p>q.size()) q.push(a[i].v);
}
while(!q.empty()){
int x=q.top();
q.pop();
ans+=x;
}
cout<<ans<<endl;
}
}