HDU 4268 Alice and Bob：Multiset 貪心匹配卡牌寬度

問題大意

Alice 和 Bob 各有 N 張卡牌，每張卡有高度 h 和寬度 w。Alice 的牌可蓋住 Bob 的牌，條件：Alice 的牌高度 ≥ Bob 的牌高度，且寬度 ≥ Bob 的牌寬度。每張牌最多用一次，求 Alice 最多能蓋住多少張 Bob 的牌。牌不能翻轉。

貪心策略

1. 將所有 2N 張牌按 高度升序 排序（高度相同時，Bob 的牌在前）。
2. 掃描排序後的序列：
   　　• 遇到 Bob 的牌 → 將其寬度插入 multiset。
   　　• 遇到 Alice 的牌 → 在 multiset 中找 不超過 Alice 寬度的最大值（即 upper_bound(w) - 1），若存在則匹配成功，計數+1，從 multiset 刪除該寬度。

這保證高度條件自然滿足（因掃描順序），寬度上用「最合適」的 Bob 牌給當前 Alice 牌，留較大寬度給後續更大的 Alice 牌，貪心最優。

C++ 代碼

#include <bits/stdc++.h>
using namespace std;
struct Node { int h, w, id; }; // id=0: Bob, 1: Alice
bool cmp(Node a, Node b) {
    if (a.h != b.h) return a.h < b.h;
    return a.id < b.id; // Bob 先
}
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        vector<Node> a(2*n);
        for (int i = 0; i < 2*n; i++) {
            scanf("%d%d", &a[i].h, &a[i].w);
            a[i].id = (i >= n); // 後 n 個是 Alice
        }
        sort(a.begin(), a.end(), cmp);
        multiset<int> s;
        int ans = 0;
        for (auto &nd : a) {
            if (nd.id == 0) s.insert(nd.w);
            else {
                auto it = s.upper_bound(nd.w);
                if (it != s.begin()) {
                    --it; ans++; s.erase(it);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 排序：\( O(N \log N) \)
• Multiset 操作：每張牌至多插入/刪除/查詢一次，共 \( O(N \log N) \)
• 總時間 \( O(N \log N) \)，空間 \( O(N) \)，N ≤ 200,000 輕鬆通過。

總結

本題是「排序 + 平衡樹貪心」的經典模型：一維排序固定一維條件，另一維用有序容器維護可用資源，每次取最合適的。multiset 的 upper_bound 配合前驅迭代器完美實現「不超過 x 的最大值」查詢。