5.推公式
AcWing 125. 耍杂技的牛
实现思路：wi表示牛的体重，si表示牛的强壮度
先给结论：按照w + s从小到大的顺序，从上往下排，最大的危险系数一定是最小的。
简单理解：把重量轻的牛放下面是很亏的，同样把不强壮的牛放下面也是亏的，所以就尽可能把又重又强壮的牛放下面。
证明：
从两方面证明：
- 按照上面策略得到的答案
>=最优解 - 按照上面策略得到的答案
<=最优解
首先，按照上面的策略得到的是一种方案，而最优解是所有方案中的最小值，所以 按照上面策略得到的答案 >= 最优解。
第二点，用反证法。假设最优解不是按照w + s从小到大排列。则一定存在一个位置i，使得wi + si > w(i+1) + s(i+1)，然后看一下把这两头牛交换，会发生什么变化。同样的，这两头牛的交换，不会影响除这两头牛以外，其他牛的危险系数，所以只看这两头牛的危险系数的变化即可。交换前和交换后，第i和第i+1头牛的危险系数如下
| 第i个位置上的牛 | 第i+1个位置上的牛 | |
|---|---|---|
| 交换前 | w1 + w2 + … + w(i-1) - si | w1 + w2 + … + wi - s(i+1) |
| 交换后 | w1 + w2 + … + w(i-1) - s(i+1) | w1 + w2 + … + w(i-1) + w(i+1) - si |
去掉公共部分 w1 + w2 + … + w(i-1)
| 第i个位置上的牛 | 第i+1个位置上的牛 | |
|---|---|---|
| 交换前 | - si | wi - s(i+1) |
| 交换后 | - s(i+1) | w(i+1) - si |
随后，对所有项加上一个 si + s(i+1)，转化为正数，方便我们比较
| 第i个位置上的牛 | 第i+1个位置上的牛 | |
|---|---|---|
| 交换前 | s(i+1) | wi + si |
| 交换后 | s(i) | w(i+1) + s(i+1) |
由于wi + si > si，且根据先前的假设，有wi + si > w(i+1) + s(i+1)
所以wi + si 大于 max(si, w(i+1) + s(i+1) ) ，进而有 max( s(i+1), wi + si) > max(si, w(i+1) + s(i+1) )。即，交换后，第i个和第i+1个位置上的牛中的最大危险系数变小了。
所以，只要存在一个位置i，使得wi + si > w(i+1) + s(i+1)，则一定能交换第i和第i+1的位置，使得总体的最大的危险系数不变或者变小。假设最优解不是按照w + s从小到大的顺序排列，则我们通过贪心策略，总是能够交换2个逆序的位置，使得到的结果，不变或者变得更小。因此，贪心得到的答案一定是 ⇐ 最优解的。
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;//存储牛的体重+强壮度，体重
const int N=50010;
PII cow[N];
int 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 sum=0,res=-2e9;
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;
return 0;
}