POJ 1456 Supermarket [貪心+并查集]

題目位址

貪心：優先選利益最大的商品，從deadline向前推直到都放不了再選下一個商品利益最大的

關鍵是判斷哪一些日子不能再放了，最簡單的方法就是一個數組+一個for循環判斷

但更快的是用并查集，p=find(deadline) 當p>0，p就是可以放的日子 否則放不了;放好後更新parent[p]=p-1;向前一天遞推

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath> 
#include<map> 
#include<vector>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
int p[10000+5];
struct product{
	int deadline,profit;
	product(int d,int p):deadline(d),profit(p){}
	bool operator < (const product& p) const {
		return profit<p.profit;
	}
};
int find(int x){
	return p[x]==x?x:p[x]=find(p[x]);
}
int main()
{
	int T;
	priority_queue<product> Q;
	while(scanf("%d",&T)!=EOF)
	{
		int pf,deadline,maxd=0;
		while(T--)
		{
			cin>>pf>>deadline;
			maxd=max(maxd,deadline);
			Q.push(product(deadline,pf));
		}
		for(int i=0;i<=maxd;i++) p[i]=i;
		int ans=0,d;
		while(!Q.empty())
		{
			d=find(Q.top().deadline);
			if(d>0){
				p[d]=d-1;
				ans+=Q.top().profit;
			}
			Q.pop();
		}
		cout<<ans<<endl;
	}
	return 0;
}