田忌赛马 题解

题目分析

本题是一个经典的贪心问题，但与传统的“田忌赛马”略有不同：

• 我们手上有 $N$ 匹马，速度分别为 $u_1, u_2, \dots, u_N$；
• 田忌手上有 $N$ 匹马，速度分别为 $v_1, v_2, \dots, v_N$；
• 田忌会按照输入给定的顺序依次派出他的马匹，而我们可以任意安排自己马匹的出场顺序；
• 所有马的速度互不相同，因此不可能出现平局。

题目要求我们找出一种安排方式，使得在 $N$ 轮比赛中，我方获胜的轮次尽可能多，并输出最多能获胜的轮数。

解题思路

关键点在于：田忌的出马顺序虽然是固定的，但由于我们可以自由调整我方马匹的出场顺序，实际上我们可以让任意一匹我方的马去迎战田忌的任意一匹马。因此，田忌马匹的出场顺序对于最终胜负没有影响——我们只需将我方的 $N$ 匹马与田忌的 $N$ 匹马进行一对一匹配，使得我方速度大于对方速度的配对数量最大化。

于是问题转化为：给定两个可重集合 $A$（我方速度）和 $B$（田忌速度），我们要在 $A$ 与 $B$ 之间建立一一匹配，求最多有多少对满足 $a>b$。

这是一个非常经典的贪心匹配问题，最优策略为：

1. 将 $A$ 和 $B$ 分别从小到大排序。
2. 用两个指针扫描：一个指针 $i$ 遍历 $A$，另一个指针 $j$ 指向 $B$ 中当前最小的、尚未被击败的马。
3. 如果 $A[i]>B[j]$，说明当前我方的马可以击败田忌当前最小的未击败马，于是配对成功，获胜数加一，同时 $j$ 向后移动，表示这匹田忌的马已被击败。
4. 如果 $A[i] \le B[j]$，说明当前我方这匹马连田忌最慢的马都赢不了，那么它也赢不了田忌剩下的任何一匹马（因为后面的马只会更快）。此时我们直接放弃这匹马（让它去输给田忌最快的马），只移动 $i$，不增加获胜数。
5. 最终答案即为成功配对的次数。

为什么这样的贪心是最优的？
因为我们总是使用“能够获胜的马中最慢的那一匹”去赢田忌“当前最慢且未被击败的马”，这样可以把更快的马保留下来，用于战胜田忌后面更快的马，从而最大化获胜机会。这其实就是经典的“田忌赛马”中“用下驷对上驷”思想的变体，只不过这里我们只关心胜场数，不关心输赢的次序。

算法说明

具体实现步骤如下：

1. 读入 $N$ 以及两个长度为 $N$ 的数组 $u$ 和 $v$。
2. 对 $u$ 和 $v$ 分别进行升序排序。
3. 初始化指针 $j = 0$（或代码中的 $h = 1$，对应数组下标从 1 开始），以及获胜计数器 $ans = 0$。
4. 遍历排序后的数组 $u$（下标 $i$ 从 $0$ 到 $N-1$ 或从 $1$ 到 $N$）：
   • 若 $u[i]>v[j]$，则 $ans$ 加 $1$，$j$ 加 $1$；
   • 否则，不做任何操作（即放弃当前 $u[i]$）。
5. 输出 $ans$。

时间复杂度分析

排序部分：对两个长度为 $N$ 的数组排序，时间复杂度为 $O(N \log N)$。
双指针扫描部分：每个数组最多被完整遍历一遍，时间复杂度为 $O(N)$。
因此总时间复杂度为 $O(N \log N)$，在 $N \le 5\times 10^4$ 的限制下可以轻松通过。

参考代码解释

以下是题目给出的 C++ 参考代码（稍作注释）：

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 100005;
5
6int a[N], t;      // a存放我方马速，t在代码中未实际使用
7int b[N], h;      // b存放田忌马速，h作为b的指针
8int n;
9
10int main() {
11    scanf("%d", &n);
12    for (int i = 1; i <= n; ++i) {
13        scanf("%d", &a[i]);
14    }
15    for (int i = 1; i <= n; ++i) {
16        scanf("%d", &b[i]);
17    }
18    h = 1;        // 田忌数组的当前指针，指向下一个待击败的最慢的马
19    t = 0;        // 未使用的变量
20    
21    sort(a + 1, a + n + 1); // 我方马速升序排序
22    sort(b + 1, b + n + 1); // 田忌马速升序排序
23    
24    int ans = 0;
25    for (int i = 1; i <= n; ++i) {
26        if (a[i] > b[h]) {  // 如果当前我方马能击败田忌最慢的未击败马
27            ++ans;          // 获胜数+1
28            ++h;            // 该匹田忌马已被击败，指针后移
29        }
30    }
31    printf("%d\n", ans);
32    return 0;
33}

代码细节说明：

• 数组下标从 $1$ 开始，因此排序使用 sort(a + 1, a + n + 1)。
• 变量 $h$ 初始为 $1$，指向田忌数组 $b$ 的第一个元素（即当前最慢且未被击败的马）。
• 在 for 循环中，每次用我方当前马 a[i] 去尝试击败 b[h]：
  • 若能击败，则计数器加一，$h$ 后移；
  • 若不能击败，则放弃这匹马，继续检查下一匹我方更快的马。
• 最后输出计数器 $ans$ 即为最多获胜轮数。

这种实现简洁且高效，完美利用了排序和贪心策略，是本题的标准解法。