题目描述
超市里有N件商品，每个商品都有利润pi和过期时间di,每天只能卖一件商品, 卖掉一件物品要用 1 的时间 ，过期商品（即当天di<=0）不能再卖。求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。
0≤N≤100000
1≤pi,di≤10000
输入描述
每组数据一行，首先一个整数 n然后 n 对数 p_i,d_i，以文件终止符结束。
输出描述
对每组数据，输出最佳收益。
样例
输入
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
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,sum,x;
pair<int,int> a[100008];
priority_queue<int,vector<int>,greater<int> > q;
int main(){
while(cin>>n){
sum=0;
for(int i=1;i<=n;i++){
cin>>a[i].second>>a[i].first;
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
q.push(a[i].second);
if(q.size()>a[i].first){
q.pop();
}
}
while(!q.empty()){
sum+=q.top();
q.pop();
}
cout<<sum<<"\n";
}
return 0;
}