(POJ - 1456) supermarket

Topic link ：1456 -- Supermarket

The original meaning of the topic is difficult to understand , Below I give a simplified version of the understanding ： There is... In the supermarket n A commodity . The first i An item must be within the shelf life （ The first di Days and before ） Sell out , If sold, the supermarket can get pi The profits of the , But you can only sell one item per day , Now you want to maximize the profits of the supermarket , What's the biggest profit , Multiple sets of data

analysis ： Greedy thoughts , That is, we first sort the goods according to the profit , It also takes a day , If you can sell the goods with high profits, sell the goods with high profits first , However, under current conditions, we can sell as late as we can （ In order to provide more time for some goods with low profit but short shelf life ）, Obviously, this is the right greedy strategy , But how do we achieve it , It is impossible for us to search for any product from its expiration date , If you find a day to sell current goods, sell , Otherwise, don't sell , This complexity is a little high , We can use the union search set to realize this process fu[i] For from i Start looking forward to the spare time you can find , The initial setting is i, Every time we use this spare time, we order fu[fu[i]]=fu[i]-1,（ if fu[i]<1 Then the commodity cannot be sold ） Because there is path compression in the process of joint search , So it will greatly reduce our query time

Here is the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=10003;
int fu[N];
struct node{
	int d,p;
}p[N];
bool cmp(node a,node b)
{
	return a.p>b.p;
}
int find(int x)
{
	if(x==fu[x]) return x;
	return fu[x]=find(fu[x]);
} 
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=10000;i++)
			fu[i]=i;
		for(int i=1;i<=n;i++)
			scanf("%d%d",&p[i].p,&p[i].d);
		sort(p+1,p+n+1,cmp);
		long long ans=0;
		for(int i=1;i<=n;i++)
		{
			int f=find(p[i].d);
			if(f>=1)
			{
				fu[f]=f-1;
				ans+=p[i].p;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}