HDU4296 Buildings（贪心）

题目链接

题意：给一堆木板堆成楼，每个木板有 w，s 两个属性。所有摆放方式中，min（每层 PDV 中的最大值）。（PDV 为该木板上面所有木板的 w 值和减去该木板 s 值）。

思路：按 s+w 排序，遍历比较。注意下数据大小要用 longlong。（因此 wa 了一发。。）

#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node{
    int w, s;
}N[100005];

bool cmp(node x, node y){
    return (x.w+x.s) < (y.w+y.s);
}

int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    while(scanf("%d", &n) != EOF){
        for(int i = 0; i < n; i++)
            scanf("%d %d", &N[i].w, &N[i].s);
        sort(N, N+n, cmp);
        long long f = 0, ans = 0;
        for(int i = 1; i < n; i++){
            f += N[i-1].w;
            ans = max(ans, f-N[i].s);
        }
        if(ans < 0) ans = 0;
        cout << ans << endl;
    }
    return 0;
}