首页 > 代码库 > POJ 3045 Cow Acrobats (想法题)

POJ 3045 Cow Acrobats (想法题)

题目链接:POJ 3045 Cow Acrobats

题意:有n只牛叠罗汉,危险指数的计算是 该层牛以上的牛重量总和减去这层牛的强度,求使最大的危险指数中的最小值。

思路:根据w+s排序,最大的在最下面,道理很简单,危险指数: sum-(w+s),(sum该层牛以上的牛重量总和)。


AC代码:


#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll __int64
using namespace std;
struct node
{
	ll w,s;
	ll sum;
};
struct node p[50010];

bool cmp(node a,node b)
{
	return a.sum<b.sum;
}
ll sum[50010];
int main()
{
	ll i;
	ll n;
	while(scanf("%I64d",&n)!=EOF)
	{
		memset(sum,0,sizeof sum);
		for(i=0;i<n;i++)
		{
			scanf("%I64d %I64d",&p[i].w,&p[i].s);
			p[i].sum=p[i].s+p[i].w;
		}
		sort(p,p+n,cmp);
		sum[0]=p[0].w;
		for(i=1;i<n;i++)
			sum[i]=sum[i-1]+p[i].w;
		ll max=sum[0]-p[0].s-p[0].w;
		for(i=1;i<n;i++)
		{
			ll temp=sum[i]-p[i].s-p[i].w;
			if(temp>max)
				max=temp;
		}
		printf("%I64d\n",max);
	}
return 0;
}


POJ 3045 Cow Acrobats (想法题)