博客

POJ1456

题目意思大概是给出很多组数据，每组数据包括利润和截止日期（单位），只要是在截止日期前能够卖出都可以，算出最大利润。每组商品必须至少花1个单位时间销售。

分析一组样例

5

100 3

200 3

300 3

80 2

20 1

最后输出的答案是600

#include <iostream>
#include <cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int f[maxn];
struct Node
{
	int pi,di;
}node[maxn];


bool cmp(Node a,Node b)
{
    return a.pi>b.pi;
}
int find(int x)
{
	if(f[x]==-1)return x;
	return f[x]=find(f[x]);
}
int main()
{
	int n;
	while(cin>>n)
	{
		memset(f,-1,sizeof(f));
		for(int i=0;i<n;i++)
		{
			cin>>node[i].pi>>node[i].di;
		}
		sort(node,node+n,cmp);
		int ans=0;
		for(int i=0;i<n;i++)
		{
			int t=find(node[i].di);
			if(t>0)
			{
				ans+=node[i].pi;
				f[t]=t-1;
			 } 
		}
		cout<<ans<<endl;
	}
	return 0;
}

对自己来说，主要是需要找到稍大利润重复截止日期的匹配，商品的销售日期匹配。

int s[maxn]; 
int find_set(int x)
{
	return x==s[x]?x:find_set(s[x]);
}

并查集的使用