奶牛玩杂技

非常棒的贪心题，我是完全没有想到解法。看了一波题解，证明如下：

若现在要处理两头牛 $a$, $b$ 记 $w$, $s$ 分别为 $w_a$ $s_a$ $w_b$ $s_b$

设在在 $a$, $b$ 上面全部牛的质量为 $w$

假设 $w_a + s_a > w_b + s_b$

若 $a$ 在上 $b$ 在下，易得

• $a$ 压扁值为 $w - s_a$
• $b$ 压扁值为 $w + w_a - s_b$

用作差法比较
$w - s_a - (w + w_a - s_b) = -s_a -w_a + s_b$

根据 $w_a + s_a > w_b + s_b$

得 $-w_b > -s_a - w_a + s_b$

即 $-s_a - w_a + s_b < 0$

所以 $w-s_a < w+w_a-s_b$

得 若最大压扁值需更新 $w+w_a-s_b$ 即为新的压扁值

若 $a$ 在下 $b$ 在下

• $b$ 压扁值为 $w - s_b$
• $a$ 压扁值为 $w + w_b - s_a$

用作差法无法讨论出谁是新的压扁值

分类讨论

• 若 $w-s_b < w+w_b-s_a$ 用作差法可得 $w+w_a-s_b > w+w_b-s_a$
• 若 $w-s_b > w+w_b-s_a$ 同理得 $w+w_a-s_b > w-s_b$

综上 $b$ 放在 $a$ 上面更优

即若牛从上到下记为 1~$n$ 必须满足 $w_i + s_i < w_{i+1} + s_{i+1}$

显然我没有证等于的情况，读者自己去想

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
struct cow {
    int w, s, sum;
}a[50000];
bool cmp(cow a, cow b){
    return a.sum < b.sum;
}
int main(){
    int ans = -2100000000, n, w=0;
    std::scanf("%d", &n);
    for (int i=0; i<n; ++i){
        std::scanf("%d%d", &a[i].w, &a[i].s);
        a[i].sum = a[i].w + a[i].s;
    }
    std::sort(a, a+n, cmp);
    for (int i=0;i<n;++i){
        ans = std::max(ans, w-a[i].s);
        w += a[i].w;
    }
    std::cout << ans;
    return 0;
}