HDU 1051 Wooden Sticks：貪心分組 (排序 + 模擬)

問題描述

有 n 根木棍，每根有長度 l 和重量 w。處理規則：先選一根，之後每次可選長度 ≥ 上一根長度**且**重量 ≥ 上一根重量的木棍。求將所有木棍分成最少組數（每組按規則處理）。

關鍵轉化

按長度**降序**排序，長度相同按重量**降序**排序。排序後，長度條件自動滿足（後選長度 ≤ 前選），問題簡化為：將重量序列分成最少**非遞增**子序列（每組重量非遞增）。

由 Dilworth 定理，最少非遞增子序列數 = 最長嚴格遞增子序列長度。但此處 n ≤ 5000，直接模擬貪心分組更簡單：

1. 遍歷排序後的木棍。
2. 對每根木棍，嘗試放入現有組中**最後一根重量 ≤ 當前重量**的組（貪心：盡量放重量大的組尾，留輕組尾給更輕的木棍）。
3. 若無合適組，新建一組。

模擬算法 (O(n²) 可接受)

sort(sticks, by l desc, w desc);
int groups = 0;
for each stick:
    bool placed = false;
    for each group:
        if (group.last_w <= stick.w) { // 可放入
            group.last_w = stick.w;
            placed = true; break;
        }
    if (!placed) create new group with stick.w;
answer = groups;

優化：組尾重量單調遞增，可用二分查找第一個 last_w > stick.w 的組，或用 multiset 維護組尾重量，O(n log n)。

參考代碼 (C++ 模擬版)

#include 
using namespace std;
struct Stick { int l, w; };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector a(n);
        for (auto &s : a) cin >> s.l >> s.w;
        sort(a.begin(), a.end(), [](Stick x, Stick y) {
            return x.l != y.l ? x.l > y.l : x.w > y.w;
        });
        vector tails; // 各組最後木棍重量
        for (auto &s : a) {
            auto it = upper_bound(tails.begin(), tails.end(), s.w);
            if (it == tails.end()) tails.push_back(s.w);
            else *it = s.w;
        }
        cout << tails.size() << '\n';
    }
    return 0;
}

關鍵點

• 排序規則：長度降序、重量降序。這將二維偏序轉化為一維「非遞增子序列分組」。
• upper_bound 找第一個 > w 的組尾，替換之；若無則新建組。等價於求最長嚴格遞增子序列長度（Patience Sorting）。
• n=5000，O(n log n) 極快，O(n²) 也能過但不推薦。

總結

• 經典二維貪心：一維排序消除一維約束，另一維做 LIS/分組。
• Patience Sorting 算法（tails 數組 + 二分）同時解決 LIS 長度與最少非遞增分組數。
• 題目也可建模為二分圖最大匹配（最小路徑覆蓋），但貪心最簡潔。