Acwing 125. 耍杂技的牛

做完这个题之后 C - Reindeer and Sleigh 2，就想起来之前做的 125. 耍杂技的牛这个题了。
知识点： 贪心
分析：
这个题的数据也是重量和力量，风险值(一头牛支撑不住的可能性)取决于它头上所有牛的总重量减去它的身体强壮程度的值

这里把该牛上方 k 头牛的体重 w 求和与自身的强壮值 s 相减。
要得到最大风险值的最小可能值， 这句话可能比较难懂，就是要让所有牛的风险值最小，然后在这些最小的风险值中找一个最大的，我的想法是让下面的牛越强壮越好，上面的牛越轻越好(反过来就是下面的牛越重越好)，这样的话就是使 越大越好。这里上次那个题是很像的。
证明：
我们假设第 i 位上的牛的 ⬅第 i+1 位的牛。
这里假设第 i 头牛是在第 i+1 头牛的上面。
按我们的想法当上面的牛的 大于下面的牛的 时我们就要进行交换

	第 i 位上的牛	第 i+1 位上的牛
交换前
交换后

交换后第 i+1 位上的牛上升，所以加上 w[i+1]。
再来分析一下风险值，我们可以看出四个值都带有 ，将它减去。

	第 i 位上的牛	第 i+1 位上的牛
交换前
交换后

很容易得到 和
现在只需要比较 和 。
当 时，，交换前更优。
当 时，， 交换后更优
由此可以得出当上面的牛的 大于下面的牛的 时我们就要进行交换。
代码实现：

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
typedef pair<int,int>PII;
const int N=5e4+5;
PII cow[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int s,w;
        cin>>w>>s;
        cow[i].x=s+w;
        cow[i].y=w;
    }
    sort(cow,cow+n);
    int sum=0,res=-1e9;
    //用来存最小的最大危险值,要用到max，所以起初定义很小。
    for(int i=0;i<n;i++)
    {
        int s=cow[i].x-cow[i].y,w=cow[i].y;
        res=max(sum-s,res);
        sum+=w;//记录总重
    }
    cout<<res;
    return;
}
signed main()
{
    int t=1;
    while(t--)
    {
        solve();
    }
}

欢迎来我的公众号参观，公众号文章链接