【bzoj1629】[Usaco2007 Demo]Cow Acrobats

2015.05.27 20:30 Wed | 11次阅读 | 旧日oi | 固定链接 | 源码

题目:
有三个头牛,下面三行二个数分别代表其体重及力量 //它们玩叠罗汉的游戏,每个牛的危险值等于它上面的牛的体重总和减去它的力量值,因为它要扛起上面所有的牛嘛. //求所有方案中危险值最大的最小
题解
贪心。。考虑两头牛的顺序,如果a.w-b.s<b.w-a.s,说明a放在上面好,按这个排下序就行,然后比较一遍,注意ans初始要设为-inf

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
#define inf 0x3f3f3f3f
struct node{
    ll w,s;
}a[50005];
int n;
ll sum=0,ans=-inf;
bool cmp(const node &a,const node &b)
{
    return a.w-b.s<b.w-a.s;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].w,&a[i].s);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,sum-a[i].s);
        sum+=a[i].w;
    }
    cout<<ans<<endl;
}```