底下的牛的强壮程度$S$越大越好
上面牛的重量和$W$越小越好(越重的放越下面)
=>
直觉是S[i]+W[i]越大的放越下面

证:

贪心得到的答案≥最优解(根据最优解定义:所有排序方案的最小值)

贪心得到的答案≤最优解

如果不是按S[i]+W[i]从小到大排序一定存在相邻i和i+1有$w_{i}+s_{i}>w_{i+1}+s_{i+1}$

• 可以发现此时交换第$i$头牛和第$i+1$头牛不影响$[0,i-1]$和$[i+2,n]$的风险

变化

第$i$个位置上的牛

第$i+1$个位置上的牛

交换前

$$w_1+…+w_(i-1)-s_i$$ $$w_1+…+w_(i)-s_(i+1)$$

交换后

$$w_1+…+w_(i-1)-s_(i+1)$$ $$w_1+…+w_(i-1)+w_(i+1)-s_(i)$$

• 前$i-1$项减去

变化

第$i$个位置上的牛

第$i+1$个位置上的牛

交换前

$$-s_i$$ $$w_(i)-s_(i+1)$$

交换后

$$-s_(i+1)$$ $$w_(i+1)-s_(i)$$

• 加上$s_{i}+s_{i+1}$

变化

第$i$个位置上的牛

第$i+1$个位置上的牛

交换前

$$s_(i+1)$$ $$w_i+s_i$$

交换后

$$s_i$$ $$w_(i+1)+s_(i+1)$$ $$w_i+s_i>s_i\\\\ w_i+s_i \geq w_(i+1)+s_(i+1)\\\\ w_i+s_i \geq max(s_i,w_(i+1)+s_(i+1))\\\\ 由w_{i}+s_{i}>w_{i+1}+s_{i+1} -> w_{i}+s_{i}>s_{i+1}-> w_{i}+s_{i}=max(s_(i+1),w_i+s_i)\\\\ max(s_(i+1),w_i+s_i) \geq max(s_i,w_(i+1)+s_(i+1))\\\\ max(交换前) \geq max(交换后)\\\\ 所有风险的最大值起码不会变大\\\\ 即只要w_{i}+s_{i}不是严格递增,则我们可以把他们变成递增的\\\\ 并且所有风险的最大值不会变大$$

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=50010;
#define x first
#define y second

int n;
PII cow[N];

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int w,s;
        cin >> w >> s;
        cow[i] = {w+s,w};
    }
    sort(cow,cow+n);
    int res = -1e9,sum=0;
    for(int i=0;i<n;i++)
    {
        int s;
        s = cow[i].x-cow[i].y;
        res = max(res,sum-s);//风险 = 上面的重量-当前的承受
        sum+=cow[i].y;
    }
    cout << res;
    return 0;
}