最能体现贪心的一个题
#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
int main()
{
int n;
while (cin >> n)
{
vector<PII> prod(n); //pair第一个数据存过期时间,第二个数据存商品利润
for (int i = 0; i < n; i ++ ) cin >> prod[i].y >> prod[i].x;
//因为要按过期时间排序,所以将过期时间放前面以便排序
sort(prod.begin(), prod.end());
priority_queue<int, vector<int>, greater<int>> heap; //小根堆,堆顶放价值最低的商品
for (auto p : prod)
{
heap.push(p.y);
//商品过期时间和利润都已排序,此时有更高利润且过期时间更长的商品加入,则剔除利润最小的商品
//注意此处可以将过期时间为1的商品全部删除,只要过期时间为2的商品利润都大于为1的,可以同时拿两件2商品
if (heap.size() > p.x) heap.pop();
}
int res = 0;
while (heap.size())
{
res += heap.top();
cout << heap.top() << endl;
heap.pop();
}
cout << res << endl;
}
return 0;
}