acwing125. 耍杂技的牛

分析

将所有奶牛按照w+s从小到大排序，计算得到的风险值即为最大（此处证明略，证明链接)

#include<iostream>
#include<algorithm>
using namespace std;
const int N=50010;
typedef pair<int ,int> PII;
int n;
PII cow[N];
int main(){
    cin>>n;
    int w,s;
    for(int i=0;i<n;i++){
        cin>>w>>s;
        cow[i]={w+s,w};
    }
    sort(cow,cow+n);//按照s+w从小到大排序
    int res=-2e9,sum=0;
    for(int i=0;i<n;i++){
        int s=cow[i].first-cow[i].second,w=cow[i].second;//获得当前的w,i
        res=max(res,sum-s);//计算最大风险
        sum+=w;//计算前i头牛的重量
    }
    cout<<res<<endl;
    
    return 0;
}