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;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 贪心