POJ1456：Supermarket(并查集版)

浅谈并查集：https://www.cnblogs.com/AKMer/p/10360090.html

堆作法：https://www.cnblogs.com/AKMer/p/10287566.html

贪心的想，我们尽量先把利润高的商品安排了。假如把利润高的物品安排在第\(x\)天，显然比安排任何利润比他低的商品在第\(x\)天更优。这就保证了我们先卖利润高的物品的贪心正确性。另外，如果能尽量把安排的日子靠后就靠后，这样拥有决策包含性的性质，这种贪心显然是最优的。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e4+5;

int n,ans;

int fa[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct Com {

	int v,t;

	bool operator<(const Com &a)const {

		return v>a.v;

	}

}p[maxn];

int find(int x) {

	if(fa[x]==x)return x;

	return fa[x]=find(fa[x]);

}

int main() {

	while(~scanf("%d",&n)) {

		for(int i=1;i<=n;i++)

			p[i].v=read(),p[i].t=read();

		sort(p+1,p+n+1),ans=0;

		for(int i=1;i<=10000;i++)fa[i]=i;

		for(int i=1;i<=n;i++) {

			int day=find(p[i].t);

			if(!day)continue;//说明没有空闲日子卖这个商品了

			ans+=p[i].v,fa[day]=day-1;

		}

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

POJ1456：Supermarket(并查集版)

最新文章

热门文章