2023年GESP四级田忌赛马解析（洛谷B3928）：C++双指针策略

15303105423 · 发表于 2025-7-9 16:40:50

本帖最后由 15303105423 于 2025-7-9 16:45 编辑

一、题目解读

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

二、解题思路

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

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

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

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

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

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

三、解题步骤
1. 输入处理：读取双方马匹数量N，分别存入u和v数组。
2. 排序：使用sort函数对u和v升序排列。
3. 双指针循环：
若u > v[j]，胜利次数+1，i和j均后移；
否则（u ≤ 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)。
五、总结
田忌赛马问题通过算法抽象，展现了策略优化的巧妙性。双指针结合排序能有效解决此类对阵问题，关键在于识别“牺牲局部换取全局最优”的策略模式。该解法不仅适用于竞赛题目，也对实际资源调度等问题具有启发意义。
来源：
2023年GESP四级田忌赛马算法解析（洛谷B3928）— C++双指针策略与代码详解