Acwing 145. 超市

Acwing 145. 超市
思路：

维护一个小跟堆，里面存放的是价值。
有一点是比较难想到的，小跟堆的size即是天数，比如里面存的是天数为3，那么里面一定不会出现3个以上的天数为3的，所以，可以保证里面最坏的情况下，所有的物品都可以卖出去。
贪心策略是，维护最大的价值，所以使用小跟堆。

代码：

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e4+10;
PII arr[N];
int n;

int main(){
    while(cin >> n){
        priority_queue<int,vector<int>, greater<int>> q;
        for(int i = 0; i < n; i++){
            cin >> arr[i].second >> arr[i].first;
        }
        sort(arr, arr + n);
        for(int i = 0; i < n; i++){
            q.push(arr[i].second);
            if(q.size() > arr[i].first) q.pop();
        }
        int ans = 0;
        while(q.size()){
            ans += q.top();
            q.pop();
        }
        cout << ans << endl;
    }
    
    
    return 0;
}