HDU 4296 Buildings：貪心排序最小化最大潛在損害值

題目大意

有 N（≤10⁵）塊樓板，每塊有重量 wᵢ 與強度 sᵢ。堆疊後，第 i 塊的潛在損害值 PDVᵢ = (上方樓板重量和) - sᵢ。求最小化整棟建築的最大 PDV，若最優值 ≤ 0 輸出 0。

貪心策略

設樓板由上至下排序。第 i 塊上方重量和為 Sᵢ = Σ_{j>i} wⱼ。
PDVᵢ = Sᵢ - sᵢ = (Σ_{j≥i} wⱼ) - wᵢ - sᵢ。
欲使最大 PDV 最小，應使 wᵢ + sᵢ 較大的樓板盡量放在上方（即優先處理）。
故按 wᵢ + sᵢ 降序排序，依序從上往下堆疊，然後計算最大 PDV。

代碼實現

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int MAXN = 100100;
typedef long long ll;

struct Floor { int w, s; } f[MAXN];

bool cmp(const Floor &a, const Floor &b) {
    return a.w + a.s > b.w + b.s;
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        ll sum = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &f[i].w, &f[i].s);
            sum += f[i].w;
        }
        sort(f, f + n, cmp);
        ll pdv = LLONG_MIN;
        for (int i = 0; i < n; ++i) {
            sum -= f[i].w; // sum 變為上方重量和
            pdv = max(pdv, sum - f[i].s);
        }
        if (pdv <= 0) puts("0");
        else printf("%lld\n", pdv);
    }
    return 0;
}

正確性證明略述

考慮相鄰兩塊樓板 A、B，若 w_A + s_A ≥ w_B + s_B，將 A 放在 B 上方不劣於相反順序。透過交換論證可推廣至整體排序最優。

複雜度

• 時間：O(N log N)（排序主導）。
• 空間：O(N)

注意

• 資料範圍 wᵢ, sᵢ ≤ 100000，N ≤ 10⁵，總重量和可能達 10¹⁰，必須用 long long。
• 輸出格式：若答案 ≤ 0 輸出 0，否則輸出數值。