AcWing 125. 耍杂技的牛

AcWing 125. 耍杂技的牛

证明看视频 吧。就是假设 换了两个元素之后不会增大结果，这样推出来的就是排序的条件。
有点像某一次周赛的最后一题堆箱子

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

const int N=50010;

typedef pair<int,int> PII;
PII a[N];
int n;

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int w,s;
        cin>>w>>s;
        a[i]={w+s,s};
    }
    sort(a,a+n);
    
    int res=-1e9;
    for(int i=0,sum=0;i<n;i++){
        int s=a[i].second,w=a[i].first-a[i].second;
        res=max(res,sum-s);
        sum+=w;
    }
    cout<<res;
    return 0;
}