HDU 1051 Wooden Sticks：貪心 + 多重集模擬求最少設置時間

問題描述

有 n (≤ 5000) 根木棍，每根有長度 l 和重量 w。機器處理第一根需 1 分鐘設置。若上一根棍子 (l, w) 滿足 l ≤ l' 且 w ≤ w'，則處理下一根 (l', w') 無需設置；否則需 1 分鐘。求處理所有棍子的最少設置時間。

核心洞察：偏序集上的最小鏈分解

定義偏序：(l₁,w₁) ≼ (l₂,w₂) ⇔ l₁≤l₂ 且 w₁≤w₂。
一組可無設置連續處理的棍子 = 一條鏈（按偏序排列）。
最少設置時間 = 將所有棍子分解為最少條鏈的數量。
由 Dilworth 定理：最少鏈分解數 = 最大反鏈大小（互不相容元素最大集合）。

貪心算法：模擬多重集「牌堆」

1. 棍子按 長度降序、長度相同則重量降序 排序。（長度相同按重量降序關鍵：避免同長不同重錯誤納入同一鏈）
2. 維護多個「牌堆」，每堆代表一條鏈的最後一根棍子（即該鏈當前最小的重量）。
3. 遍歷排序後的棍子 (l, w)：
   • 在現有牌堆中找重量 ≥ w 的最小堆頂（即能接在後面的最「緊」鏈）。
   • 若找到，替換該堆頂為 w（延長該鏈）；
   • 否則開新堆（新鏈）。
4. 最終堆數即為最少設置時間。

為什麼長度降序、重量降序？

長度降序保證：處理到某棍子時，所有可能作為其前驅的棍子（長度 ≥ 它）已處理完畢。
同長度按重量降序：若同長不同重，重的在前。因長度相等時需重量也 ≤ 才能無設置接續，重的先處理可作為較輕的前驅；若輕的在前，重的無法接在後面（重量不滿足 ≤），會錯誤開新堆。

數據結構優化：multiset + upper_bound

牌堆堆頂重量保持有序。對當前重量 w，需找 第一個 > w 的元素（即最小的 ≥ w+1）。用 multiset：

sort(sticks.begin(), sticks.end(), [](a,b){
    return a.l != b.l ? a.l > b.l : a.w > b.w;
});
multiset tops;
for (auto& s : sticks) {
    auto it = tops.upper_bound(s.w); // 第一個 > w
    if (it != tops.end()) tops.erase(it);
    tops.insert(s.w);
}
cout << tops.size() << '\n';

upper_bound 返回第一個 > key 的迭代器，正好是「最小的 ≥ w+1」。若所有堆頂 ≤ w，則返回 end()，需開新堆。

複雜度

• 排序：O(n log n)
• 每根棍子一次 multiset 操作：O(log n)
• 總計：O(n log n)，n=5000 瞬間通過

樣例驗證

輸入：5 根 (4,9) (5,2) (2,1) (3,5) (1,4)
排序後：(5,2) (4,9) (3,5) (2,1) (1,4)
模擬：堆數 = 2 ✓

總結

HDU 1051 是二維偏序最小鏈分解的經典應用。排序轉化為一維問題，multiset 貪心模擬牌堆，代碼極簡、效率高。掌握「降序排序 + upper_bound 找最小可接堆」模板，可解決大類相似問題（如導彈攔截、信封嵌套等）。