AcWing125. 耍杂技的牛(贪心+推公式)

题目链接AcWing125. 耍杂技的牛

分析:
这是一道贪心问题，我们假设牛最终的摆放顺序(从上大小)为1,2,3,...i,i+1,...,n，当存在相邻的两头牛i,i+1如果 $w_i+s_i>w_{i+1}+s_{j+1}$ 那么交换两头牛i,i+1的位置，后所有牛风险值的最大值不会变大。
证明:
首先，可以容易想到交换两头牛i,i+1的位置不会对1~i-1和i+1~n牛的风险值产生影响
我们将1~i-1头牛的重量表示为 $w_{上}$
那么，
第i头牛的风险值为 $w_{上}?s_i$
第i+1头牛的风险值为 $w_{上}+w_i?s_{i+1}$
此时，两头牛i,i+1的最大风险值为 $\max (w_{上}?s_i,w_{上}+w_i?s_{i+1})$
交换两头牛i,i+1的位置后
第i头牛的风险值为 $w_{上}?s_{i+1}$
第i+1头牛的风险值为 $w_{上}+w_{i+1}?s_i$
此时，两头牛i,i+1的最大风险值为 $\max (w_{上}?s_{i+1},w_{上}+w_{i+1}?s_i)$
因为 $w_i+s_i\ge w_{i+1}+s_{j+1}$ ,所以有 $w_i?s_{i+1}\ge w_{i+1}?s_{ji}$
所以有:
$w_{上}+w_i?s_{i+1}>w_{上}+w_{i+1}?s_i$
$w_{上}+w_{i+1}?s_i>w_{上}?s_i$
$w_{上}+w_i?s_{i+1}>w_{上}?s_{i+1}$
所以有$\max (w_{上}?s_i,w_{上}+w_i?s_{i+1})>\max (w_{上}?s_{i+1},w_{上}+w_{i+1}?s_i)$
所以，存在相邻的两头牛i,i+1如果 $w_i+s_i>w_{i+1}+s_{j+1}$ 那么交换两头牛i,i+1的位置，后所有牛风险值的最大值会变小。
类似于冒泡排序的思路，可以用贪心的思想来找到该问题的一个最优解，就是按照 $w_i+s_i$从小到大的顺序从高往低摆放牛

代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=5e4+10;
typedef pair<int,int> pii;
typedef long long ll;
vector<pii> v;

int main(){
    int n;
    int res=-1e9;
    cin>>n;
    for(int i=0;i<n;i++){
        int w,s;
        scanf("%d%d",&w,&s);
        v.push_back({w+s,w});
    }
    sort(v.begin(),v.end());
    ll ans=0;
    for(int i=0;i<v.size();i++){
        if(ans-v[i].first+v[i].second>res) res=ans-v[i].first+v[i].second;

        ans+=v[i].second;
    }
    cout<<res;
    return 0;
}