题目描述

超市里有N件商品，每个商品都有利润$p_i$和过期时间$d_i$,每天只能卖一件商品，过期商品（即当天$d_i$<=0）不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

输入格式
输入包含多组测试用例。

每组测试用例，以输入整数N开始，接下里输入N对$p_i和d_i$，分别代表第i件商品的利润和过期时间。

在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。

输出格式
对于每组产品，输出一个该组的最大收益值。

每个结果占一行。

数据范围
$0≤n≤10000$
$1≤p_i,d_i≤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

二叉堆(priority_queue)+贪心

这道题目,我们很容易发现是有一个贪心性质,也就是对于t天,我们需要在保证不卖出过期商品的前提下,卖出利润前t大的商品.

所以呢,我们可以把商品按照过期时间排序,然后建立一个小根堆,对于每一个数而言,如果说它的过期时间大于当前小根堆的个数,那么我们可以直接将这个货物的价值加入进来,如果说当前过期时间正好等于这个小根堆堆内的个数,那么我们就需要对比一下,如果说这个货物的价值,是高于小根堆的堆顶的话,那么我们就将小根堆堆顶弹出,然后push我们这个新货物,因为新货物明显是更加优于堆顶的老货物的

C++ 代码

//POJ,本地都过了,然而这里TLE挂掉了.
#include <bits/stdc++.h>//POJ不可使用bits库,自己只能手打其他库
#pragma G++ optimize (2)
#pragma C++ optimize (2)
using namespace std;
const int N=10100;
priority_queue<int,vector<int>,greater<int> > p;
pair<int,int> a[N];
int n,m,i,j;
inline void read(int& x)//快速读入
{
    x=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        x=x*10+c-'0',c=getchar();
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if (n==0)
        {
            puts("0");
            continue;
        }
        for(int i=1; i<=n; i++)
        {
            read(a[i].second);//pair排序是以first为第一关键字,因为我们是时间为第一关键字,所以我们读入权值是第二关键字.
            read(a[i].first);
        }
        sort(a+1,a+1+n);
        for(int i=1; i<=n; i++)
        {
            if (a[i].first>p.size())
                p.push(a[i].second);
            else if(a[i].first==p.size() && a[i].second>p.top())
            {
                p.pop();
                p.push(a[i].second);
            }
        }
        long long ans=0;
        while(!p.empty())
        {
            ans+=p.top();
            p.pop();
        }
        printf("%lld\n",ans);
    }
    return 0;
}