【题解】P1842 奶牛玩杂技

P1842 奶牛玩杂技

SOL:

构造相邻的两头牛，看能不能贪心，且看需要满足什么条件的时候才能贪心。
设有相邻的两头牛a,b，来讨论一下在满足什么条件的的情况下a放在b上面比b放在a上面更优：

设放在a,b上面的牛的总重为W

i：a放在b上面
a的压扁值：W-Sa
b的压扁值：W+Wa-Sb

ii:b放在a上面
a的压扁值：W+Wb-Sa
b的压扁值：W-Sb

要使a放在b上面比b放在a上面更优，
则max(W-Sa,W+Wa-Sb,) < max(W+Wb-Sa,W-Sb);
易证W-Sa < W+Wb-Sa,W-Sb<W+Wa-Sb;

那就转化成了使W+Wa-Sb<W+Wb-Sa;
->Wa+Sa < Wb+Sb

综上，当满足这个条件的时候，a放在b上面比b放在a上面更优；

那么我们以Wi+Si为关键字从小到大排序，（此时已经确立各奶牛的位置），那我们从上到下利用前缀和扫一遍最小的压扁值就好啦。

int n,m;
const int N=5e4+10;
struct nainiu{
    int s,w;
    bool operator < (const nainiu &rhs)const{
        return s+w<rhs.s+rhs.w; //贪心 
    }
}cow[N];

#undef int
int main(){
#define int long long
    #ifdef WIN32
    freopen("test.txt","r",stdin);
    #endif
    rd(n);
    rep(i,1,n){
        rd(cow[i].w),rd(cow[i].s);
    }
    sort(cow+1,cow+n+1);
    int sum=0,ans=INT_MIN;
    rep(i,1,n){
        ans=max(ans,sum-cow[i].s);
        sum+=cow[i].w;
    }
    printf("%d",ans);
    return 0; 
}

【题解】P1842 奶牛玩杂技

原文：https://www.cnblogs.com/sjsjsj-minus-Si/p/11655917.html