算法案例 04：渊子赛马博弈算法求解#

本报告探讨赛马博弈问题中的贪心匹配算法与胜负预测模型。

---

一、 题目描述#

渊子与对手各有 $n$ 匹马参加比赛，已知所有马的速度均恒定且各不相同。比赛采用一对一两两对决，胜场数超过一半（不含一半）者获胜。

设计算法输入双方马匹速度，预测渊子是否能赢得比赛。

---

二、 贪心匹配算法设计（田忌赛马策略）#

为了让渊子获得尽可能多的胜场，采用最优贪心对决策略：

1. 将渊子的马速数组 $A$ 与对手的马速数组 $B$ 分别按从大到小排序；
2. 比较渊子当前最快的马 $A[\text{fast}]$ 与对手最快的马 $B[\text{fast}]$：
   • 若 $A[\text{fast}] > B[\text{fast}]$：直接让 $A[\text{fast}]$ 与 $B[\text{fast}]$ 比赛（赢得一场）；
   • 若 $A[\text{fast}] \le B[\text{fast}]$：用渊子当前最慢的马 $A[\text{slow}]$ 去消耗对手当前最快的马 $B[\text{fast}]$；
3. 统计渊子的总胜场数 $W$，若 $W > n / 2$，预测渊子获胜，否则无法获胜。

---

三、 C++ 算法实现#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool predictYuanziWin(vector<int> yuanzi, vector<int> opponent) {
    int n = yuanzi.size();
    sort(yuanzi.begin(), yuanzi.end());
    sort(opponent.begin(), opponent.end());

    int y_slow = 0, y_fast = n - 1;
    int o_slow = 0, o_fast = n - 1;
    int wins = 0;

    while (y_slow <= y_fast) {
        if (yuanzi[y_fast] > opponent[o_fast]) {
            wins++;
            y_fast--;
            o_fast--;
        } else if (yuanzi[y_slow] > opponent[o_slow]) {
            wins++;
            y_slow++;
            o_slow++;
        } else {
            // 用最慢的马抵挡对手最快的马
            y_slow++;
            o_fast--;
        }
    }

    return wins > (n / 2);
}

int main() {
    vector<int> yuanzi = {92, 83, 71, 60};
    vector<int> opponent = {95, 87, 74, 55};

    bool canWin = predictYuanziWin(yuanzi, opponent);
    cout << "预测渊子比赛结果: " << (canWin ? "胜利 (WIN)" : "失败 (LOSE)") << endl;

    return 0;
}

---

四、 复杂度与结果结论#

• 时间复杂度：$O(n \log n)$（主要开销在于排序）；
• 该贪心策略保证在已知对手速度时能够得出渊子所能达到的最大胜场数。