Farmer John 养了N(1<=N<=50,000)头牛，她们已经按1~N依次编上了号。FJ所不知道的是，他的所有牛都梦想着从农场逃走，去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的的秋千上站稳（她们还尝试过把自己装在大炮里发射出去，但可想而知，结果是悲惨的） 。最终，她们决定练习一种最简单的杂技：把所有牛都摞在一起， 比如说， 第一头牛站在第二头的身上， 同时第二头牛又站在第三头牛的身上...最底下的是第 N头牛。
每头牛都有自己的体重以及力量，编号为 i 的奶牛的体重为
W_i(1<=W_i<=10,000)，力量为 S_i(1<=S_i<=1,000,000,000)。
当某头牛身上站着另一些牛时它就会在一定程度上被压扁，我们不妨把它被压扁的程度叫做它的压扁指数。对于任意的牛，她的压扁指数等于摞在她上面的所有奶牛的总重（当然不包括她自己）减去它的力量。奶牛们按照一定的顺序摞在一起后， 她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。
你的任务就是帮助奶牛们找出一个摞在一起的顺序，使得总压扁指数最小。
第一行：N
接下来N行，每行两个数：Wi和Si
最小总压扁指数
3
10 3
2 5
3 3
2
【解题思路】
记每头牛的重量为w,力量为s,w+s=sum，存在结构体数组t中。
对每头牛的sum值进行排序，要证明sum值大的牛放在底下是最优解。
证明sum值最大的牛放在最下面最优即可。
证明：当sum值最大时，有两种可能：（注：这只是一种形象的说法）
1.若w值较大，则将其放在最下方，不让它压其他牛；
2.若s值较大，则将其放在最下方，承受其他牛的压力。
所以将sum值大的牛放在下方即可。
【code】
1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 using namespace std;
5 int n,W,ans=-1<<30;
6 struct Node{
7 int w;
8 int s;
9 }a[50005];
10 inline bool cmp(const Node a,const Node b){
11 return a.w+a.s>b.w+b.s;
12 }
13 int main(){
14 //freopen("1842.in","r",stdin);
15 //freopen("1842.out","w",stdout);
16 scanf("%d",&n);
17 for(register int i=1;i<=n;i++){
18 scanf("%d%d",&a[i].w,&a[i].s);
19 W+=a[i].w;
20 }
21 sort(a+1,a+n+1,cmp);
22 for(register int i=1;i<=n;i++){
23 W-=a[i].w;
24 if(W-a[i].s>ans)ans=W-a[i].s;
25 }
26 printf("%d\n",ans);
27 return 0;
28 }
原文：https://www.cnblogs.com/66dzb/p/11582015.html