你有 N 匹马可自由安排出场,田忌按顺序出马,速度两两不同,求最多能赢几轮。
你和田忌各有 N 匹马,进行 N 轮比赛,每轮各出一匹决胜负。你的马速度是 u₁…u_N,田忌的马速度是 v₁…v_N。田忌会按给定顺序出马,而你可以自由安排自己马匹的出场顺序。
所有马的速度两两不同,不会出现平局。求最多能赢几轮。
贪心双指针最大匹配排序
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N;第二行你的 N 匹马速度;第三行田忌的 N 匹马速度 |
| 输出 | 最多获胜轮数 |
| 数据范围 | 1 ≤ N ≤ 5 × 10⁴ |
| 速度范围 | 1 ≤ uᵢ, vᵢ ≤ 2N |
| 关键前提 | 所有速度两两不同(保证无平局) |
u[i] > v[j] 就赢一轮(i、j 都前进);否则这匹马赢不了任何对手,直接放弃(i 前进)双方排序后(本来就有序)开始双指针。
| 步骤 | i(你的马) | j(对手的马) | 比较 | 结果 | 已赢轮数 |
|---|---|---|---|---|---|
| 初始 | u[0] = 1 | v[0] = 2 | 1 > 2?否 | 放弃 1,i 右移 | 0 |
| 第 1 次 | u[1] = 3 | v[0] = 2 | 3 > 2?是 | 赢!i、j 都右移 | 1 |
| 第 2 次 | u[2] = 5 | v[1] = 4 | 5 > 4?是 | 赢!i、j 都右移 | 2 |
| 第 3 次 | i 越界 | — | — | 结束 | 2 |
对手最慢的马速度是 2
我们的 1 连它都跑不过,说明打不过任何对手
所以直接放弃,不浪费和它对位的机会
❌ 放弃
3 对 2 → 赢;5 对 4 → 赢;1 对 6 → 输
共赢 2 轮,与题面解释一致
✅ 答案 2
最多赢 2 轮 ✓
你的马:10 3 5 8 7 → 排序后 3 5 7 8 10
对手的马:4 6 1 2 9 → 排序后 1 2 4 6 9
| 步骤 | 你的马 | 对手的马 | 比较 | 结果 | 已赢轮数 |
|---|---|---|---|---|---|
| 1 | 3 | 1 | 3 > 1 ✅ | 赢 | 1 |
| 2 | 5 | 2 | 5 > 2 ✅ | 赢 | 2 |
| 3 | 7 | 4 | 7 > 4 ✅ | 赢 | 3 |
| 4 | 8 | 6 | 8 > 6 ✅ | 赢 | 4 |
| 5 | 10 | 9 | 10 > 9 ✅ | 赢 | 5 |
五轮全胜 ✓
双方升序排序,用两个指针扫一遍统计胜利数
for (i = 0, j = 0; i < N && j < N; ) if (u[i] > v[j]) { win++; i++; j++; } else i++;——只有一行循环体。把每匹你的马能赢的对手马连边,求最大匹配
| 方案 | 时间复杂度 | N = 5 × 10⁴ 时 |
|---|---|---|
| 排序 + 双指针 | O(N log N) | 约 8 × 10⁵(可行) |
| 二分图匹配 | O(N × E) | 约 10⁹ 以上(超时) |
第一行输入你的马(空格分隔),第二行输入田忌的马。程序会给出最优配对阵。
点按钮开始 →
#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++,因为我们放弃的是自己的马);③ 误以为要考虑田忌的出马顺序(因为我们可以自由排自己的马,顺序不影响答案)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 2 | 题面样例 1 |
5 | 5 | 题面样例 2(全胜) |
1 | 1 | 一匹马,赢了 |
1 | 0 | 一匹马,输了 |
3 | 0 | 全部弱于对手,一场都赢不了 |
4 | 4 | 全面强于对手,全胜 |
i++),因为对手那匹马还要留给后面的强马去对位。需要存两个数组。
✅ 80 万次操作,瞬间完成。如果硬套二分图匹配,会超时——识别问题的特殊结构很重要。
// 双指针贪心的通用模板(两个有序序列找最大匹配) 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:若要"最小化损失",可用类似思路反向扫描 // 另一经典写法(从大到小对位) // 用最大的马打对手最大的马:能赢就赢,不能赢就用自己的最弱马去"送"
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 双指针贪心 | 两个有序序列配对 | 赛马、任务分配、区间匹配 |
| 识别特殊结构 | 胜负关系有传递性 → 贪心最优 | 避免不必要的通用算法 |
| 最大匹配 | 二分图通用解法 | 一般图/二分图匹配问题 |