推公式

5.推公式

AcWing 125. 耍杂技的牛

实现思路：wi表示牛的体重，si表示牛的强壮度

先给结论：按照w + s从小到大的顺序，从上往下排，最大的危险系数一定是最小的。

简单理解：把重量轻的牛放下面是很亏的，同样把不强壮的牛放下面也是亏的，所以就尽可能把又重又强壮的牛放下面。

证明：

从两方面证明：

• 按照上面策略得到的答案 >= 最优解
• 按照上面策略得到的答案 <= 最优解

首先，按照上面的策略得到的是一种方案，而最优解是所有方案中的最小值，所以 按照上面策略得到的答案 >= 最优解。

第二点，用反证法。假设最优解不是按照w + s从小到大排列。则一定存在一个位置i，使得wi + si > w(i+1) + s(i+1)，然后看一下把这两头牛交换，会发生什么变化。同样的，这两头牛的交换，不会影响除这两头牛以外，其他牛的危险系数，所以只看这两头牛的危险系数的变化即可。交换前和交换后，第i和第i+1头牛的危险系数如下

去掉公共部分 w1 + w2 + … + w(i-1)

随后，对所有项加上一个 si + 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个逆序的位置，使得到的结果，不变或者变得更小。因此，贪心得到的答案一定是 <= 最优解的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#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;
}