简单注释

一个问题：按照如下证明得到的结果成了分情况讨论，也没有得到到底为啥排序后最优的结果。。。哪位小伙伴清楚可以给俺指点一二！

参考代码：

// 与"国王游戏"一样

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5e4 + 10;

int n;
PII cow[N];

// 按照s + w从小到大排序
// 证明：假设最终答案不是按照s + w从小大大排序的，则一定存在逆序对 w[i] + s[i] > w[i + 1] + s[i + 1]
// 考虑变化前后i位置和i + 1位置的牛 
//                  i位置                               i + 1位置
// 交换后  w[0]+w[1]+...+w[i-1]+w[i+1]-s[i]      w[0]+w[1]+...+w[i-1]-s[i+1]
// 交换前  w[0]+w[1]+...+w[i-1]-s[i]             w[0]+w[1]+...+w[i-1]+w[i]-s[i+1]

// 公共部分去掉
// w[i+1]-s[i]      -s[i+1]
// -s[i]            w[i]-s[i+1]

// 同时加s[i]+s[i+1]得
// w[i+1]+s[i+1]        s[i]
// s[i+1]               w[i]+s[i]

// 由于都是正数 交换前最大值为w[i]+s[i]
// 由基础条件知道 w[i]+s[i] > w[i+1]+s[i+1] 且 w[i]+s[i] > s[i]，所以如果存在逆序对，则交换后更优 没有逆序对则交换前更优
// 证明也是不是很符合逻辑。。。成了分情况讨论了

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 = -2e9, sum = 0;
    for(int i = 0; i < n; i++){
        int w = cow[i].second, s = cow[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }
    cout << res << endl;
    return 0;
}