现在有N块积木，每块积木都有自重Weight和正常状态下的承重能力Force，现在要把这N块积木垒在一起，但是有可能某块积木的负重超过了它在正常状态下的承重能力，那么这块积木就有被压坏的危险，请问应该如何堆这N块积木使得N块积木中最大的压力指数最小。
这里定义压力指数为该积木的负重与其在正常状态下的承重能力的差值。
原题：Usaco NOV05 Sliver 奶牛杂技(Cow Acrobats)
第一行为一个正整数N，表示有N块积木。
第二行到第 N+1 行，每行两个整数数，分别是第i个积木的Weight和Force。
输出共一行，表示最大压力指数的最小值。
2
100 0
1000 100
0
样例解释：
把Weight为100的积木放在Weight为1000的积木上，下面积木的压力指数为100 - 100 = 0，另外一块积木的压力指数和它的相等。
对于30% 的数据，1 <= N <= 3
对于60% 的数据，1 <= N <= 1000
对于100%的数据，1 <= N <= 50000
对于100%的数据，1 <= Weight <= 10000，1 <= Force <= 109
分析：第一关键字w+h升序，第二关键字w升序排序，扫描一遍
代码：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; struct node{ int w,f,s; }a[100010];int n,ans=-698987979; int cmp(node a,node b){ if(a.s<b.s) return 1; if(a.s>b.s) return 0; if(a.w<b.w) return 1; /*if(a.s==b.s) return a.w<b.w;//等价 return a.s<b.s;*/ } int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d",&a[i].w,&a[i].f); a[i].s=a[i].w+a[i].f; } sort(a,a+n,cmp); int c=0; for(int i=0;i<n;i++){ ans=max(ans,c-a[i].f); c+=a[i].w; } printf("%d\n",ans); return 0; }
原文：http://www.cnblogs.com/shenben/p/5539818.html