貪心算法經典：田忌賽馬問題（HDU 1052）完整解析與 C++ 實現

問題重述

田忌與齊王各有 n 匹馬（n ≤ 1000），速度已知。每場比賽派一匹馬，贏得 +200，平 0，輸 -200。求田忌最大期望收益。

貪心策略核心邏輯

雙方馬速排序後，維護四個指標：

• t_slow, t_fast：田忌最慢/最快馬索引
• k_slow, k_fast：齊王最慢/最快馬索引

每輪決策（優先級順序）：

1. 若 t[t_slow] > k[k_slow]：用最慢馬贏對方最慢馬 → ++t_slow; ++k_slow; ans++
2. 若 t[t_fast] > k[k_fast]：用最快馬贏對方最快馬 → --t_fast; --k_fast; ans++
3. 若 t[t_slow] < k[k_fast]：用最慢馬犧牲對方最快馬 → ++t_slow; --k_fast; ans--
4. 否則（剩餘馬速相等）：
   • 若 t[t_slow] < k[k_fast]：同上犧牲
   • 否則平局 → ++t_slow; --k_fast（不增減分）

正確性證明大綱

1. 贏局最大化：能贏時優先用最弱馬贏，保留強馬應對更強對手。
2. 輸局最小化：必輸時用最弱馬犧牲對方最強馬，減少損失。
3. 平局處理：當最強馬相等時，若最弱馬能贏對方最弱馬則贏；否則犧牲最弱馬換平局，不劣於其他策略。
4. 透過交換論證與歸納法可證該策略為全域最優。

完整 C++ 實現（含註釋）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n && n) {
        vector t(n), k(n);
        for (int &x : t) cin >> x;
        for (int &x : k) cin >> x;
        sort(t.begin(), t.end(), greater()); // 降序：索引 0 為最快
        sort(k.begin(), k.end(), greater());

        int t_slow = n-1, t_fast = 0;
        int k_slow = n-1, k_fast = 0;
        int score = 0;

        while (t_slow >= t_fast) {
            if (t[t_slow] > k[k_slow]) {          // 最慢贏最慢
                ++score; ++t_slow; ++k_slow;
            } else if (t[t_fast] > k[k_fast]) {   // 最快贏最快
                ++score; --t_fast; --k_fast;
            } else {
                if (t[t_slow] < k[k_fast]) --score; // 犧牲最慢換最快
                ++t_slow; --k_fast;
            }
        }
        cout << score * 200 << '\n';
    }
    return 0;
}

複雜度分析

• 排序：O(n log n)
• 貪心匹配：O(n)
• 空間：O(n)

測試樣例

常見錯誤提醒

• 排序方向混淆：降序時索引 0 為最大值，邊界條件需對應調整。
• 平局情況未正確處理犧牲邏輯，導致分數偏高。
• 使用 int 足夠（n≤1000，分數範圍 ±200,000）。

延伸變體

• 雙方馬數不等：補虛擬馬速度 0。
• 引入權重：轉為最大權重二分圖匹配（KM 算法）。
• 多測試案例讀取至 EOF 或 0 終止。