POJ 1456 Supermarket：貪心 + 並查集優化調度最大化利潤

題目大意

n 種商品 (n≤10000)，每種有利潤 p 和截止日期 d (d≤10000)。每天最多賣一種。安排銷售計劃最大化總利潤。

貪心策略

1. 按利潤 **從大到小排序**。
2. 對於當前商品，嘗試在其截止日期 d 當天安排。若已被佔用，向前找最近的空閒天。
3. 若找到 (天數 ≥ 1)，安排上，累加利潤；否則放棄該商品。

並查集優化「向前找空閒天」

維護 `father[i]` = 當前天數 i 可用的最近空閒天 (含自己)。初始 `father[i]=i`。
安排第 d 天後，`father[d] = find(d-1)` (合併到前一天)。
查找 `find(d)` 即為最近可用天。路徑壓縮使查找均攤 O(α(n))。

代碼實現 (C++)

#include 
#include 
using namespace std;

const int MAXN = 10005;

struct Product { int p, d; } a[MAXN];
int father[MAXN];

bool cmp(Product a, Product b) { return a.p > b.p; }

int find(int x) {
    return father[x] == x ? x : father[x] = find(father[x]);
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) scanf("%d%d", &a[i].p, &a[i].d);
        sort(a, a+n, cmp);
        for (int i = 0; i <= 10000; i++) father[i] = i;
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int d = find(a[i].d);
            if (d > 0) {
                father[d] = d - 1; // 佔用 d 天，合併到 d-1
                ans += a[i].p;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

對比：無並查集版本

// 暴力向前找，最壞 O(n*d) 可能 TLE
bool used[10005] = {false};
for (int i = 0; i < n; i++) {
    int d = a[i].d;
    while (d > 0 && used[d]) d--;
    if (d > 0) { used[d] = true; ans += a[i].p; }
}

關鍵點

• 貪心證明：高利潤優先安排最晚可能日期，給低利潤留出更早靈活日期。
• 並查集將「向前線性掃描」優化為「近似 O(1) 跳躍」。
• 截止日期上限 10000，父數組大小 10001 足夠。
• 多測試用例以 EOF 結束。