POJ 1456 Supermarket

Question

Solution

想到贪心。
我们可以对于物品按照截止日期从小到大排序。
然后倒着枚举，每次讲一个物品的价值加入大根堆中。
我们可以保证当前可以购买大根堆里面的任何东西。
但要满足最优解，那就贪心选最大。
操作数就是两两之间的时间差。

code

#include<cstdio>
#include<algorithm>
#define N 10010
using namespace std;
struct node{int profit,end;}a[N];
int n,d[N],top=0,ans=0;

int cmp(node x,node y) {return x.end==y.end ? x.profit<y.profit : x.end<y.end;}

void up(int x)
{
	while (x>1 && d[x]>d[x>>1])
		swap(d[x],d[x>>1]),x>>=1;
}

void down()
{
	int x=1,t=x<<1;
	if (t<top && d[t]<d[t+1]) t++;
	while (t<=top && d[t]>d[x])
	{
		swap(d[t],d[x]);
		x=t,t=x<<1;
		if (t<top && d[t]<d[t+1]) t++;
	}
}

int main()
{
	freopen("supermarket.in","r",stdin);
	freopen("supermarket.out","w",stdout);
	while (scanf("%d",&n)!=EOF)
	{
		for (int i=1,x,y;i<=n;i++)
			scanf("%d%d",&a[i].profit,&a[i].end);
		sort(a+1,a+n+1,cmp);
		a[0]=(node){0,0};ans=0;
		d[top=1]=a[n].profit;
		for (int i=n-1;i>=0;i--)
		{
			for (int j=a[i].end;j<a[i+1].end;j++)
			{
				if (!top) break;
				ans+=d[1],d[1]=d[top--];
				down();
			}
			d[++top]=a[i].profit,up(top);
		}
		printf("%d
",ans);
	}
	return 0;
}

PS：网上说有什么并查集解法。。。

转载需注明出处。