核心思想: 贪心
推公式: 将 i 和 i+1 个奶牛交换位置
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII; //first存w+s second存w
PII cows[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int w,s;
cin>>w>>s;
cows[i] = {w+s,w};
}
sort(cows,cows+n); //根据key排序
int res = -2e9,sum = 0;
for(int i=0;i<n;i++)
{
int w = cows[i].second,s = cows[i].first - w;
res = max(res, sum - s); //求危险系数最大值
sum += w; //用于求危险系数
}
cout<<res;
}