HDU 4296 Buildings （YY）

題意： 給定N個物體，每個物體有兩個參數w，s。   w代表它自身的重量； s代表它的強度。現在要把這些物體疊在一起，會產生一個PDV值。 PDV解釋：(Σwj)-si, where (Σwj) stands for sum of weight of all floors above.即為在i物體上方所有物體的重量和 - i的強度。 現在希望最大的PDV值最小....................   YY： 假設兩個物體i，j，把誰放上面比較好？ 假設把i放上面，則pdv1 = Wi - Sj；把j放上面 則pdv2 = Wj - Si；要使得pdv盡量小，設pdv1 < pdv2 則 Wi +　Si < Wj + Sj   所以按照w+s由小到大sort，就能滿足條件了......  

#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include<functional>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <string>  
#include <vector>  
#include <set>  
#include <queue>  
#include <stack>  
#include <climits>//形如INT_MAX一類的  
#define MAX 100005  
#define INF 0x7FFFFFFF  
using namespace std;  
  
struct node {  
    int w,s;  
}a[MAX];  
int n;  
  
bool cmp(const node &x, const node &y) {  
    return x.w + x.s < y.w + y.s;  
}  
int main() {  
    while(scanf("%d",&n) != EOF) {  
        for(int i=0; i<n; i++) {  
            scanf("%d%d",&a[i].w,&a[i].s);  
        }  
        sort(a,a+n,cmp);  
        __int64 sum = 0;  
        __int64 pdv = -INF;  
        for(int i=1; i<n; i++) {  
            sum += a[i-1].w;  
            pdv = max(pdv,sum - a[i].s);  
        }  
        if(pdv < 0) printf("0\n");  
        else printf("%I64d\n",pdv);  
    }  
    return 0;  
}