奶牛玩杂技题解

经验分享区
1
奶牛玩杂技

题目大意：每头牛都有自己的体重以及力量，编号为 i 的奶牛的体重为 W_i ，力量为 S_i 。当某头牛身上站着另一些牛时它就会在一定程度上被压扁，我们不妨把它被压扁的程度叫做它的压扁指数。对于任意的牛，她的压扁指数等于摞在她上面的所有奶牛的总重（当然不包括她自己）减去它的力量。奶牛们按照一定的顺序摞在一起后， 她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。

思路概述：贪心，就是重量大的往下放，然后力气大也是如此。
假设只有两只奶牛，一只奶牛的重量为 W1 ，力气为 S1 。
另一只奶牛的重量为 S1 ，力气为 S2 。
如果前者在下压扁指数即为 𝑊2−𝑆1 。
如果后者在下压扁指数即为 𝑊1−𝑆2 。
假设前者在下更优即为前者在下压扁指数更小
那么 𝑊2−𝑆1<W1−S2 移项得 𝑊2+𝑆2<𝑊1+𝑆1 这个时候是处于前者在下更优的情况下所以得出结论 𝑊𝑖+𝑆𝑖 越大就应该越往下放

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
struct node
{
	int w,s;
}a[N];
int n,m;
bool cmp(node a,node b)
{
	return a.w+a.s<b.w+b.s;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].w,&a[i].s);
	}
	sort(a+1,a+n+1,cmp);
	int ans=-1e9,tmp=0;
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,tmp-a[i].s);
		tmp+=a[i].w;
	}
	printf("%d",ans);
	return 0;
}
1 个赞