算法进阶指南83页 POJ 1456

超市里有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
思路：我们按照过期时间顺序从小到大排序 小根堆中放的使我们当前选择的最优解
1.如果当前商品的过期时间 t 等于堆中元素的个数，前 t 天将把堆中的商品卖出 若此商品的价值小于堆顶元素（最优解的最小值）则用新的商品来代替堆顶元素
2. 如果当时商品过期时间 t 大于堆的元素个数 即代表没有过期 直接进堆

#include<bits/stdc++.h>
using namespace std;
const int N = 10000 + 10 ;
typedef long long ll;
struct node
{
    int v,d;
    bool operator < (const node & oth) const{
        if(d == oth.d) {
            return v > oth.v;
        }
        return d < oth.d;
    }
}a[N];
int n;
int main()
{
    //freopen("in.txt","r",stdin);
    while( ~scanf("%d",&n)){
        for(int i = 1 ,v ,d; i <= n ;i++){
            scanf("%d %d",&v , &d);
            a[i] = {v , d};
        }
        sort(a + 1,a + 1 + n);
        priority_queue<int , vector <int > ,greater<int> > q;
        for(int i = 1 ;i <= n ;i ++){
            if(a[i].d > q.size()){
                q.push(a[i].v);
            }
            else if(a[i].d == q.size()){
                if(a[i].v > q.top()){
                    q.pop();
                    q.push(a[i].v);
                }
            }
        }
        ll res = 0;
        while(q.size()){
            res += q.top() ;
            q.pop();
        }
        printf("%lld\n",res);
    }
    return 0;
}