2023年GESP四级田忌赛马算法解析（洛谷B3928）— C++双指针策略与代码详解

一、题目解读

“田忌赛马”源自中国古代典故，田忌通过策略性安排马匹对阵顺序，以弱马对阵强马、强马对阵弱马的方式，实现整体胜利。在算法竞赛中，该问题通常转化为：给定两方马匹的战斗力数组，如何通过对阵策略最大化获胜场次。洛谷B3928题目要求计算在最优策略下，田忌能获得的胜利次数。

二、解题思路

核心思路为“排序 + 双指针策略”：

1. 预处理：对双方马匹战斗力排序，确保我方马匹从弱到强（u数组），田忌马匹同样排序（v数组）。

2. 策略核心：通过双指针i（我方马）和j（田忌马）遍历：

    若我方当前最弱马能赢田忌当前最弱马（u[i] > v[j]），则获胜，双指针均后移；

    若无法获胜，则用我方最弱马对阵田忌最强马（策略性输掉），仅移动我方指针i，保留更强马匹后续对战。

3. 最终获胜次数由遍历中累计的胜利计数得出。

三、解题步骤

1. 输入处理：读取双方马匹数量N，分别存入u和v数组。

2. 排序：使用sort函数对u和v升序排列。

3. 双指针循环：

    若u[i] > v[j]，胜利次数+1，i和j均后移；

    否则（u[i] ≤ v[j]），仅i后移，策略性输掉比赛。

4. 输出结果：累计的胜利次数。

四、代码与注释

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 优化输入输出速度
    
    int N;
    cin >> N; // 输入马匹数量
    
    vector<int> u(N), v(N); // 存储双方马匹战斗力
    for (int i = 0; i < N; ++i) cin >> u[i];
    for (int i = 0; i < N; ++i) cin >> v[i];
    
    // 对双方马匹进行排序
    sort(u.begin(), u.end());
    sort(v.begin(), v.end());
    
    int wins = 0; // 获胜次数
    int i = 0, j = 0; // 双指针：i指向我方马，j指向田忌马
    
    // 双指针策略遍历
    while (i < N && j < N) {
        if (u[i] > v[j]) { // 我方弱马能赢田忌弱马
            ++wins; // 胜利次数+1
            ++i; ++j; // 双指针后移
        } else { // 我方弱马无法赢
            ++i; // 策略性输掉，仅移动我方指针
        }
    }
    
    cout << wins << endl;
    return 0;
}

注释说明：代码通过预处理排序和双指针的“策略性输掉”机制，将田忌赛马的策略转化为算法实现，时间复杂度O(NlogN)。

五、总结

田忌赛马问题通过算法抽象，展现了策略优化的巧妙性。双指针结合排序能有效解决此类对阵问题，关键在于识别“牺牲局部换取全局最优”的策略模式。该解法不仅适用于竞赛题目，也对实际资源调度等问题具有启发意义。