POJ 1456 Supermarket：貪心 + 并查集調度最大獲利

問題建模

N 件商品，每件有利潤 p 和截止日期 d。每天只能賣一件，必須在截止日期前（含當天）賣出。求最大利潤。

貪心策略

按利潤**從大到小排序**。對每件商品，嘗試在其截止日期 d 或之前最晚的空閒天賣出。若找到則累加利潤，標記該天已用。

并查集優化查找可用天

• `father[i]` 表示第 i 天可用的最晚天（初始 `father[i]=i`）
• 第 i 天被占用後，`father[i] = find(i-1)`，指向前一天
• `find(x)` 路徑壓縮查找 x 可用的最晚天
• 若 `find(d) > 0` 則可安排，否則放棄該商品

正確性

高利潤優先 + 安排在最晚可用天，保留早期天給截止日期早的商品，經典調度問題最優解。

複雜度

排序 O(N log N)，并查集操作近似 O(α(N))，總體 O(N log N)。N ≤ 10000 極快。