HDU 4268 Alice and Bob：貪心 + multiset 卡片覆蓋遊戲

問題描述

Alice 和 Bob 各有 n 張卡片，卡片有長寬 (x,y)。Alice 的卡片長寬均不小於 Bob 的卡片時可覆蓋。每張卡片只能用一次，不可旋轉。求 Alice 最多能覆蓋多少張 Bob 的卡片。

貪心策略

• 將雙方卡片按長度降序排序 (長相同則寬降序)。
• 遍歷 Alice 的卡片，維护一个 multiset 存儲「長度 ≤ 當前 Alice 卡片長度」的所有 Bob 卡片的寬度。
• 在 multiset 中找最大寬度 ≤ Alice 當前寬度的元素 (upper_bound 前一個)，若存在則覆蓋成功，計數++，從 multiset 中刪除該元素。

證明：對於當前 Alice 卡片，選擇能覆蓋的 Bob 卡片中寬度最大的，留給後續 (長度更小) 的 Alice 卡片更寬鬆的寬度餘量，符合貪心最優子結構。

複雜度

• 排序：O(n log n)。
• 遍歷 + multiset 操作：O(n log n)。
• 總體 O(n log n)，n ≤ 100,000 可行。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
struct Card { int x, y; };
bool cmp(const Card& a, const Card& b) {
    return a.x != b.x ? a.x > b.x : a.y > b.y;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector A(n), B(n);
        for (auto& c : A) cin >> c.x >> c.y;
        for (auto& c : B) cin >> c.x >> c.y;
        sort(A.begin(), A.end(), cmp);
        sort(B.begin(), B.end(), cmp);
        multiset ms;
        int ans = 0, j = 0;
        for (int i=0;i