耍杂技的母牛（母牛叠罗汉问题）

问题：

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

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

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

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

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

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

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

思路：

贪心算法的思想，将每个母牛的强壮程度和体重相加，再将其从小到大排序。这样能求出风险值最大的最小值。

设按照上述规则求得的答案为可行解c n t cntcnt 最优解为a n s ansans

运用反证法：

代码实现：

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N=100010;
int n;
typedef pair<int,int> PII;PII cows[N];int main() 
{scanf("%d",&n);for(int i=0;i<n;i++){int w,s;scanf("%d%d",&w,&s);cows[i]={w+s,w};	}sort(cows,cows+n);int res=-2e9,sum=0;for(int i=0;i<n;i++){int w=cows[i].second; res=max(res,sum-cows[i].first+w);sum+=cows[i].second;}cout<<res;return 0;}
/*
输入：310 32 53 3
输出：2*/