Supermarket

题目描述

有一个商店有许多批货，每一批货又有N(0<=N<=10^4)个商品,同时每一样商品都有收益Pi,和过期时间Di(1<=Pi,Di <=10^4)，一旦超过了过期时间，商品就不能再卖。

你要做的就是求出每批货最多能得到多少收益。

输入输出格式

输入格式

多组数据，每组先给出一个整数N，表示这批货的商品个数。

然后有N对数，每对数有两个用空格隔开的正整数P_i,D_i,表示第i个商品的收益和过期时间。相邻两对数之间用空格隔开。

输入以一个文件终止符结束，并且保证所有输入数据正确。

输出格式

对于每组数据，输出一行一个整数表示该批货物能卖出的最大价格。

输入输出样例

输入

输出

思路

毫无疑问这题可以用贪心的思想来做：价值越大越优先考虑，并且按其最晚天数卖出，如果天数已经被占用则往前寻找未使用的天数。至于为什么，相信你可以理解。实现：用一个结构体来装商品的价值与最迟天数，并将其按价值降序排列，价值一样，天数降序排，在开个数组记录天数是否用过。

分析：

不过发现这题还可以用堆来做，于是用堆来重新做一次。也用到了贪心的思想。先将所有商品按过期时间从小到大排序，然后建立一个商品价值的小根堆，依次遍历每个商品，如果发现当前堆的size小于过期日期，则说明现在卖出的商品个数小于其过期日期，就可以直接将该商品的价值丢进堆中;如果发现当前堆的size等于过期日期，则说明直到该商品的过期日期为止每一天都已经有商品卖出了，则比较当前商品价值与堆顶元素大小，如果大于，就将堆顶删除，再将该商品丢进堆中。最后堆中剩下的元素就是我们要卖出的元素，求和输出即可。

WA

首先我们应该比较价值，而不是比较货物到期的时间。 （First we should compare value instead of the time when the goods have expired.）

#include<bits/stdc++.h>
using namespace std;
struct node{
    int p;
    int d;
}sp[10001];
int cmp(node x,node y){
    if(x.d!=y.d){
        return x.d<y.d;
    }
    else{
        return x.p>y.p;
    }
}
int main(){
    int n;
    int vis;
    while(cin>>n){
        memset(sp,0,sizeof(sp));
        for(int i=1;i<=n;i++){
            cin>>sp[i].p>>sp[i].d;
        }
        sort(sp+1,sp+n+1,cmp);
        int ans=0;
        vis=1;
        for(int i=1;i<=n;i++){
            if(sp[i].d>=vis){
                if(sp[i].p>=0){
                    ans+=sp[i].p;
                    vis++;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

AC

#include<bits/stdc++.h>
using namespace std;
struct node{
    int p;
    int d;
}sp[10001];
int cmp(node x,node y){
    if(x.p!=y.p){
        return x.p>y.p;
    }
    else{
        return x.d<y.d;
    }
}
int main(){
    int n;
    int vis;
    while(cin>>n){
        memset(sp,0,sizeof(sp));
        for(int i=1;i<=n;i++){
            cin>>sp[i].p>>sp[i].d;
        }
        sort(sp+1,sp+n+1,cmp);
        int ans=0;
        int vis[n+1];
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++){
            if(sp[i].p>=0){
                for(int j=sp[i].d;j>=1;j--){
                    if(vis[j]==0){
                        ans+=sp[i].p;
                        vis[j]=1;
                        break;
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}