Supermarket

题目

有一个商店有许多批货，每一批货又有N个商品，同时每一样商品都有收益Pi，和过期时间Di，一旦超过了过期时间，商品就不能再卖。

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

输入

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

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

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

输出

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

输入样例

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
           

数据范围

0 <= n <= 10000

1 <= Pi <= 10000

1 <= Di <= 10000

思路

这道题可以用贪心配上并查集来做。

我们把商品按收益从大到小排序，然后一个一个枚举，用过期时间来并查集，如果卖，那么当前时间就不能卖其他的商品了，就只能在前一秒卖了。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct note
{
	int p,d;
}a[10001];
int n,f[10001],ans;
int find(int x)//并查集
{
	return f[x]==-1?x:f[x]=find(f[x]);
}
bool cmp(note x,note y)//按收益从大到小排序
{
	return x.p>y.p;
}
int main()
{
	while (scanf("%d",&n)!=EOF)//读入
	{
		memset(f,-1,sizeof(f));//初始化
		ans=0;//初始化
		for (int i=1;i<=n;i++) 
		scanf("%d%d",&a[i].p,&a[i].d);//读入
		sort(a+1,a+n+1,cmp);//按收益从大到小排序
		for (int i=1;i<=n;i++)
		{
			int now=find(a[i].d);//用过期时间来并查集
			if (now)//判断能否卖
			{
				ans+=a[i].p;//卖出去
				f[now]=now-1;//当前时间就不能再卖其他东西了，指向前一秒
			}
		}
		printf("%d\n",ans);//输出收益
	}
	return 0;
}
           

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------