HDU 4296 Buildings 公式证明贪心的正确性
题意：有n（1<=n<=100000）块地板，每块有wi自身重量和si承重重量，每一块地板有对应的PDV = sum（wj above） - si，
现在想安排一种摆放方案使得max（PDVi）最小。
题解：现在考虑相邻的两块i j，设上方sigama(wi) = sum，i 在 j上方时分别得到PDVi = sum - si，PDVj = sum + wi - sj，同理得到j在i上方时
PDVjj = sum - sj，PDVii = sum + wj - si，若i在j上方始终优于j在i上方，则MAX（PDVi ， PDVj） < MAX（PDVii ， PDVjj）,
推出wi + si < wj + sj 为i在j上方的解更优的充要条件。所以可以推出从上到下i + si递减为最优解，此时最下面的PDV最大。
Sure原创，转载请注明出处。
#include <iostream>#include <cstdio>using namespace std;int n;inline void in(long long &a){ char ch; while(ch = getchar(), ch < '0' || ch > '9'); a = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') { a = a * 10 + ch - '0'; } return;}void solve(){ long long sum = 0,s = 0; long long x,y; for(int i=0;i<n;i++) { in(x),in(y); sum += x; if(x + y > s) s = x + y; } printf("%I64d\n",sum-s); return;}int main(){ while(~scanf("%d",&n)) { solve(); } return 0;}