P2878 [USACO07JAN]保护花朵Protecting the Flowers

一个类似国王游戏的贪心

话说要是先做了这个题，国王游戏之余懵逼这么久吗？

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

struct node

{

	long long t;

	long long d;

};

node data[101000];

bool compare(const node &a,const node &b)

{

	return a.d*b.t>b.d*a.t;

}

int main()

{

	int n;

	scanf("%d",&n);

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

		scanf("%d%d",&data[i].t,&data[i].d);

	sort(data+1,data+1+n,compare);

	long long sum=0;

	long long tim=0;

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

	{

		sum+=data[i].d*=tim;//牛都吓傻了

		tim+=data[i].t*2;

	}

	printf("%lld",sum);

}

巴特西

P2878 [USACO07JAN]保护花朵Protecting the Flowers

最新文章

热门文章