GESP 题解库 / 4 级题解 / [GESP202312 四级] 田忌赛马 · 第 16 / 25 题
GESP202312 四级 · B3928 · 简单

田忌赛马

你有 N 匹马可自由安排出场,田忌按顺序出马,速度两两不同,求最多能赢几轮。

📊
N ≤ 5 × 10⁴
马匹数量
🔢
速度 ≤ 2N
数值范围
⚡
O(N log N)
时间复杂度
🎯
排序 + 双指针贪心
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

你和田忌各有 N 匹马,进行 N 轮比赛,每轮各出一匹决胜负。你的马速度是 u₁…u_N,田忌的马速度是 v₁…v_N。田忌会按给定顺序出马,而你可以自由安排自己马匹的出场顺序。

所有马的速度两两不同,不会出现平局。求最多能赢几轮。

💡
人话翻译:虽然题目强调"田忌按顺序出马",但你可以自由安排自己的出场顺序,所以顺序其实不重要——本质是"最多能凑出多少对 (你的马, 对手的马) 使得你的更快",也就是一个最大匹配问题。经典解法:双方都排序,然后用双指针贪心。

🔍 关键词提取

贪心双指针最大匹配排序

已知条件

项目说明
输入第一行 N;第二行你的 N 匹马速度;第三行田忌的 N 匹马速度
输出最多获胜轮数
数据范围1 ≤ N ≤ 5 × 10⁴
速度范围1 ≤ uᵢ, vᵢ ≤ 2N
关键前提所有速度两两不同(保证无平局)

需要解决的问题

02
思维导图
整理解题思路的全貌
🐎 双方排序 + 双指针
📥 读入
N ≤ 5 × 10⁴
你的马 u[]
对手的马 v[]
速度两两不同
🔢 排序
u 升序
v 升序
排序后贪心才有效
O(N log N)
🎯 双指针
i 扫自己的马,j 扫对手
u[i] > v[j] → 赢,i、j 都加 1
否则 i 加 1(放弃这匹马)
赢不了最慢的必然全输
⚠️ 易错点
忘记排序
比较写成 ≥(速度不同无需考虑)
指针越界
误以为要考虑田忌的出马顺序
03
样例手算推导
样例 1 与样例 2 的双指针过程

🧮 样例 1:u = 1 3 5,v = 2 4 6,答案 2

双方排序后(本来就有序)开始双指针。

步骤i(你的马)j(对手的马)比较结果已赢轮数
初始u[0] = 1v[0] = 21 > 2?否放弃 1,i 右移0
第 1 次u[1] = 3v[0] = 23 > 2?是赢!i、j 都右移1
第 2 次u[2] = 5v[1] = 45 > 4?是赢!i、j 都右移2
第 3 次i 越界——结束2
1
为什么放弃速度 1 的马?

对手最慢的马速度是 2

我们的 1 连它都跑不过,说明打不过任何对手

所以直接放弃,不浪费和它对位的机会

❌ 放弃

2
配对结果

3 对 2 → 赢;5 对 4 → 赢;1 对 6 → 输

共赢 2 轮,与题面解释一致

✅ 答案 2

最多赢 2 轮 ✓

🧮 样例 2:答案 5(全胜)

你的马:10 3 5 8 7 → 排序后 3 5 7 8 10
对手的马:4 6 1 2 9 → 排序后 1 2 4 6 9

步骤你的马对手的马比较结果已赢轮数
1313 > 1 ✅赢1
2525 > 2 ✅赢2
3747 > 4 ✅赢3
4868 > 6 ✅赢4
510910 > 9 ✅赢5

五轮全胜 ✓

🔑
注意"排序后逐位比较"就够了:把双方升序排好后,只要我们的第 k 小马比对手的第 k 小马快,就能一路对位获胜。双指针的写法本质上就是在做这件事——用我们的"最小能赢的马"去击败对手的"最慢的马",把强的马留到后面。
04
解法对比
双指针贪心 vs 二分图匹配

⚔️ 解法对比

🟢 排序 + 双指针(推荐) 推荐

双方升序排序,用两个指针扫一遍统计胜利数

  • 时间 O(N log N)
  • N = 5 × 10⁴ 轻松通过
  • 代码 8 行
  • 不需要建图
💡
核心代码:for (i = 0, j = 0; i < N && j < N; ) if (u[i] > v[j]) { win++; i++; j++; } else i++;——只有一行循环体。

🟠 二分图最大匹配

把每匹你的马能赢的对手马连边,求最大匹配

  • 时间 O(N × E) 或更复杂
  • N = 5 × 10⁴ 时不可行
  • 严重超时
  • 完全没必要
⚠️
为什么不用:这个问题有一个很好的结构——胜负关系满足"传递性"(若 A 能赢 B,B 能赢 C,则 A 能赢 C),所以贪心最优,不需要通用匹配算法。

📈 性能对比

方案时间复杂度N = 5 × 10⁴ 时
排序 + 双指针O(N log N)约 8 × 10⁵(可行)
二分图匹配O(N × E)约 10⁹ 以上(超时)
05
算法流程图
双方排序后双指针扫描
开始读入 N,你的马 u[]、对手的马 v[]把 u 和 v 分别升序排序i = 0,j = 0,win = 0u[i] > v[j] 吗?是 ✓win 加 1,i、j 都加 1否 ✗i 加 1(放弃这匹马)i 或 j 越界了吗?输出 win结束两边都还有马 → 继续比较
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🐎 赛马对阵计算器

第一行输入你的马(空格分隔),第二行输入田忌的马。程序会给出最优配对阵。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

int u[50005], v[50005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &u[i]);
    for (int i = 0; i < n; i++) scanf("%d", &v[i]);

    sort(u, u + n);      // 双方升序排序
    sort(v, v + n);

    int i = 0, j = 0, win = 0;
    while (i < n && j < n) {
        if (u[i] > v[j]) {       // 能赢对手最慢的马
            win++;
            i++;
            j++;                 // 两匹马都用掉了
        } else {
            i++;                 // 连最慢的都赢不了,这匹马放弃
        }
    }

    printf("%d\n", win);
    return 0;
}
🔑
贪心的正确性怎么理解?对手最慢的马 v[j] 迟早要有人去对位。如果我们有一匹马能赢它,用"刚好能赢它的那匹"(即当前最小的能赢它的马)去对位最划算,因为更强的马可以用来对付对手更强的马。如果连最小的都不能赢它,那这匹马赢不了任何对手,直接放弃即可。

📖 关键几行怎么看

代码作用为什么这样写
sort(u, u + n); sort(v, v + n);双方排序排序后才能用双指针贪心
if (u[i] > v[j])判断能否获胜速度两两不同,不会相等,用 > 即可
win++; i++; j++;赢一轮两匹马都消耗掉了
else i++;放弃当前马连对手最慢的都赢不了,留着也没用
⚠️
三个坑:① 忘记排序(双指针贪心必须建立在有序基础上);② 把放弃的分支写成 j++(应该是 i++,因为我们放弃的是自己的马);③ 误以为要考虑田忌的出马顺序(因为我们可以自由排自己的马,顺序不影响答案)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
1 3 5
2 4 6
2题面样例 1
5
10 3 5 8 7
4 6 1 2 9
5题面样例 2(全胜)
1
5
3
1一匹马,赢了
1
3
5
0一匹马,输了
3
1 2 3
4 5 6
0全部弱于对手,一场都赢不了
4
10 20 30 40
1 2 3 4
4全面强于对手,全胜
✅
自查清单:① 双方都排序了吗?② 放弃时移动的是 i 吗?③ 循环条件是 i、j 都未越界吗?

🚨 易错点清单

⚠️
忘记排序:不排序就双指针会得到错误答案。
⚠️
放弃时写成 j++:放弃的应该是自己的马(i++),因为对手那匹马还要留给后面的强马去对位。
⚠️
以为要考虑田忌的顺序:题目允许我们自由安排出场,所以顺序无关,只需求最大获胜匹配数。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N log N)
空间复杂度
O(N)
N 最大
5 × 10⁴
运算量
约 8 × 10⁵

时间怎么算的?

空间都用在哪?

需要存两个数组。

✅ 80 万次操作,瞬间完成。如果硬套二分图匹配,会超时——识别问题的特殊结构很重要。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 双指针贪心的通用模板(两个有序序列找最大匹配)
sort(a, a + n); sort(b, a + n);
int i = 0, j = 0, cnt = 0;
while (i < n && j < m) {
    if (a[i] > b[j]) { cnt++; i++; j++; }   // 匹配成功
    else i++;                                 // 当前 a[i] 太小,放弃
}

// 变体 1:若要"最多平局或胜利",把 > 改为 >=
// 变体 2:若要"最小化损失",可用类似思路反向扫描

// 另一经典写法(从大到小对位)
// 用最大的马打对手最大的马:能赢就赢,不能赢就用自己的最弱马去"送"

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
双指针贪心两个有序序列配对赛马、任务分配、区间匹配
识别特殊结构胜负关系有传递性 → 贪心最优避免不必要的通用算法
最大匹配二分图通用解法一般图/二分图匹配问题
🌟
思考题:如果题目改成"求最小可能的获胜轮数"(即最差情况下你只能赢几场),该怎么算?(提示:这等价于"求对手的最大获胜匹配",把角色互换、用同样的双指针算法算出对手最多赢多少,再用 N 减去它即可。)