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;}