貪心算法經典：田忌賽馬（HDU 1052）策略證明與 C++ 實現

問題重述

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

貪心策略（雙雙指標法）

將雙方馬速由快到慢排序，維護四個指標：

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

每輪決策：

1. 若 t_fast > k_fast：最快勝最快，score += 200; t_fast--; k_fast--;
2. 若 t_slow > k_slow：最慢勝最慢，score += 200; t_slow++; k_slow++;
3. 否則：
   　　若 t_slow < k_fast：最慢犧牲最快，score -= 200; t_slow++; k_fast--;
   　　否則（相等）：最慢與最快平局，t_slow++; k_fast--;

正確性直觀證明

• 能贏的局面優先用最小代價贏（最慢勝最慢、最快勝最快）；
• 必輸的局面用最廢棋犧牲（最慢對最快）；
• 平局情況下，保留強力馬應付後續，犧牲最弱馬；
• 此策略等價於在雙邊有序序列上尋找最大權匹配，貪心選擇具有最優子結構。

C++ 參考代碼

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

int main() {
    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<int>());
        sort(k.begin(), k.end(), greater<int>());

        int tf = 0, ts = n-1, kf = 0, ks = n-1;
        int score = 0;
        while (tf <= ts) {
            if (t[tf] > k[kf]) { score += 200; tf++; kf++; }
            else if (t[ts] > k[ks]) { score += 200; ts--; ks--; }
            else {
                if (t[ts] < k[kf]) score -= 200;
                ts--; kf++;
            }
        }
        cout << score << '\n';
    }
    return 0;
}

複雜度分析

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