HDU 1338：遊戲預測——貪心策略求最少勝場

題目大意

雙方各 n 張牌（值 1..n·m），我方牌面已知，對方牌面未知但可推斷。我方按升序出牌，對方每次用能贏的最小牌壓制，否則棄最小牌。求我方最少贏多少局。

貪心證明

對方最優策略：對我方出的牌，若有更大的牌則用「剛好贏」的最小牌；否則棄最小牌。這等價於雙方都按升序，對方嘗試用最小贏牌對應我方每張牌。

算法流程

1. 我方牌排序
2. 標記所有牌（1..n·m）是否為我方持有
3. 遍歷我方牌從小到大：
   • 找對方比它大的最小牌 → 標記已用
   • 找不到 → 對方剩餘牌全比我方小，我方全贏，累加剩餘局數並結束

C++ 實現

#include <cstdio>
#include <algorithm>
using namespace std;
int my[55], used[1005];
int n, m, T;

int find_min_greater(int x) {
    for (int i = x+1; i <= T; ++i)
        if (!used[i]) return i;
    return 0;
}

int main() {
    int kase = 1;
    while (scanf("%d%d", &m, &n) == 2 && (n||m)) {
        T = n * m;
        fill(used, used+T+1, 0);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &my[i]);
            used[my[i]] = 1;
        }
        sort(my+1, my+n+1);
        int lose = 0;
        for (int i = 1; i <= n; ++i) {
            int opp = find_min_greater(my[i]);
            if (opp) used[opp] = 1;
            else { lose = n - i + 1; break; }
        }
        printf("Case %d: %d\n", kase++, lose);
    }
    return 0;
}

複雜度

• 時間：O(n·T) ≈ 50 × 5000 = 2.5×10⁵，極快
• 空間：O(T)