POJ - 1456 Suprtmarket

POJ - 1456 Suprtmarket

题目大意：传送门

有\(n\)个物品，第\(i\)个物品必须要在\(d_i\)天内买完，且卖出该物品可以获得\(p_i\)的利润。一天只能卖一个物品，求最多可以获得多少利益

题目分析：

每天可以卖一件商品，那么每天卖的物品一定要是不超过期限的物品中最贵的一个物品。

我们最后一天卖的物品一定是期限为\(d_{max}\)的物品中最贵的物品

第\(d_{max}-1\)天卖的物品则一定是期限小于等于\(d_{max}-1\)的物品或者其余期限为\(d_{max}\)的物品中最贵的物品

以此类推

此题为贪心题，我们可以用并查集优化时间复杂度

我们可以按价格降序排列，对于每个商品，如果时间和之前的商品没有冲突，那么就直接卖出。如果发生了冲突，那么就说明这一天不能卖商品了，就将发生冲突的商品的期限减一天（该过程可能发生多次）。

如何用并查集维护？

用并查集维护原期限为d的商品的新期限

find(d)<1:期限小于1，无法卖出

find(d)>=1:可以卖出，卖出之后p[find(d)]=find(d)-1;

题目代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e4 + 10;
int n, p[N];

struct node
{
	int val, day;
}inf[N];

bool cmp(struct node a, struct node b)
{
	return a.val > b.val;
}

int find(int x)
{
	if (p[x] != x)
		p[x] = find(p[x]);
	return p[x];
}

int main()
{
	while (cin >> n)
	{
		for (int i = 0; i < N; i++) //初始化p[i]=i,期限为i的商品的最初期限为i
		{
			p[i] = i;
		}

		for (int i = 1; i <= n; i++)
		{
			cin >> inf[i].val >> inf[i].day;
		}
		sort(inf + 1, inf + 1 + n, cmp);

		int ans = 0;
		for (int i = 1; i <= n; i++)
		{
			int day = find(p[inf[i].day]);
			if (p[day] < 1)
				continue;
			else
			{
				ans += inf[i].val;
				p[day] = day - 1; //期限减一天
			}
		}
		cout << ans << endl;
	}
}