证明转自: here
题意：有 n 个地板，每个地板 i 有两个权值 Wi, Si，且 PDV(i) = (ΣWj) - Si ( j 表示在 i 上面的地板)。问如何调整顺序，使得【max(PDV)】最小。
思路：假设i,j相邻，并且i上面的重量为sum,若i在上面，则有pi=sum-si,pj=sum+wi-sj;若j在上面，则有pi‘=sum+wj-si,pj‘=sum-sj;
显然有pi<pi‘,pj>pj‘,于是令pj<pi‘,就有sum+wi-sj<sum+wj-si，即wi+si<wj+sj;
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 #define MAXN 100010 8 typedef long long ll; 9 struct Node { 10 int w,s; 11 } node[MAXN]; 12 int n; 13 14 int cmp(const Node &p,const Node &q) { 15 return p.w+p.s<q.w+q.s; 16 } 17 18 int main() { 19 while(~scanf("%d",&n)) { 20 for(int i=1; i<=n; i++) { 21 scanf("%d%d",&node[i].w,&node[i].s); 22 } 23 sort(node+1,node+1+n,cmp); 24 ll sum=0,MAX=0; 25 for(int i=1; i<=n; i++) { 26 MAX=max(MAX,sum-node[i].s); 27 sum+=node[i].w; 28 } 29 printf("%I64d\n",MAX); 30 } 31 return 0; 32 }
原文：http://www.cnblogs.com/cnblogs321114287/p/4356767.html