AcWing 125 耍杂技的牛

题意

题目连接：https://www.acwing.com/problem/content/127/

农民约翰的N头奶牛（编号为1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这N头奶牛中的每一头都有着自己的重量Wi以及自己的强壮程度Si。

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入格式
第一行输入整数N，表示奶牛数量。

接下来N行，每行输入两个整数，表示牛的重量和强壮程度，第i行表示第i头牛的重量Wi以及它的强壮程度Si。

输出格式
输出一个整数，表示最大风险值的最小可能值。

数据范围
1≤N≤50000,
1≤Wi≤10,000,
1≤Si≤1,000,000,000

解题思路

注意，这里求的是所有牛中风险值最大的那个。核心是求得一个排列，按照什么进行排列是关键。

推理1：可以想到，一头牛a如果位置已经确定了，并且这头牛下面的牛的位置也已经确定了，那么牛a上面的牛无论怎么排列都不会影响这头牛的风险值，因为风险值仅仅和牛a上面牛的重量和和牛a本身的强壮值决定。

首先，我们先假设已经有这样的一个排列，使得风险值最小，既然是最优，那么如果交换了两个相邻的牛，结果会发生生么呢？答案是变得不那么“好”了（也有可能是好的，比如这两头牛w和s的值完全相同）。

而且根据上面的推理1可以推出，交换了两个相邻的牛，仅仅影响这两头牛的风险值，而不会影响其他牛的风险值。于是，我们可以试图找出到底是什么因素导致交换后结果不那么“好”了。

这里用了网上的一个图来说明交换前后的风险值。

这样，通过上面的图，交换前的一列和交换后的一列值进行比较

通过上面的分析，交换后变得不“好”的条件是w+s值大的放到比较高的位置了。

拓展一个排列不等式

下面摘自百度

排序不等式表述如下，设有两组数a1,a2,……an和b1,b2,……bn，满足a1≤a2≤……≤an,b1≤b2≤……≤bn，c1,c2,……cn是b1,b2,……bn的乱序排列，则有a1bn+a2bn-1+……+anb1≤a1c1+a2c2+……+ancn≤a1b1+a2b2+……+anbn,当且仅当a1=a2=……=an或b1=b2=……=bn时等号成立。一般为了便于记忆，常记为：反序和≤乱序和≤顺序和.

代码实现

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 5E4+7;
struct Node{
    ll w, s;
    friend bool operator < (const Node &a, const Node &b){
        return a.w + a.s > b.s + b.w;
    }
};
Node node[MAXN];
int n;

int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>node[i].w>>node[i].s;
    }
    sort(node, node+n);
    ll pre = node[n-1].w;
    ll ans = -node[n-1].s;
    for(int i=n-1-1; i>=0; i--){
        ans = max(ans, pre-node[i].s);
        pre += node[i].w;
        // cout<<pre<<endl;
    }
    cout<<ans<<endl;
    return 0;
}