【GESP】C++四级真题 luogu-B3928 [GESP202312 四级] 田忌赛马
GESP C++四级2023年12月真题。本题为一维数组和排序的应用练习，难度⭐⭐★☆☆。本题在洛谷评定为普及-。
本质上说，这里的算法策略采用的是贪心策略，属于GESP五级的内容，但是作为四级考生，在忽略所谓对贪心策略理解的情况下，也可以通过自己的思考解决。
luogu-B3928 [GESP202312 四级] 田忌赛马
题目要求
题目描述
你要和田忌赛马。你们各自有 $N$ 匹马，并且要进行 $N$ 轮比赛，每轮比赛，你们都要各派出一匹马决出胜负。
你的马匹的速度分别为 $u_1,u_2,\cdots，u_n$，田忌的马匹的速度分别为 $v_1,v_2,\cdots,v_n$。田忌会按顺序派出他的马匹，请问你要如何排兵布阵，才能赢得最多轮次的比赛？巧合的是，你和田忌的所有马匹的速度两两不同，因此不可能出现平局。
输入格式
第一行一个整数 $N$。保证 $1\le N \le 5\times 10^4$
接下来一行 $N$ 个用空格隔开的整数，依次为 $u_1,u_2,\cdots,u_n$，表示你的马匹们的速度。保证 $1\le u_i\le 2N$。
接下来一行 $N$ 个用空格隔开的整数，依次为 $v_1,v_2,\cdots,v_n$，表示田忌的马匹们的速度。保证 $1\le v_i\le 2N$。
输出格式
输出一行，表示你最多能获胜几轮。
输入输出样例 #1
输入 #1
1
2
3
3
1 3 5
2 4 6
输出 #1
1
2
输入输出样例 #2
输入 #2
1
2
3
5
10 3 5 8 7
4 6 1 2 9
输出 #2
1
5
说明/提示
样例解释 1:
第 1 轮，田忌派出速度为 2 的马匹，你可以派出速度为 3 的马匹迎战，本轮你获胜。
第 2 轮，田忌派出速度为 4 的马匹，你可以派出速度为 5 的马匹迎战，本轮你获胜。
第 3 轮，田忌派出速度为 6 的马匹，你可以派出速度为 1 的马匹迎战，本轮田忌获胜。
如此，你可以赢得 2 轮比赛。
题目分析
题目分析
本题主要考察一维数组、排序和贪心算法的应用。
解题思路：
- 数据预处理
- 读入双方马匹数量N和各自马匹速度数组
- 对双方马匹速度数组进行排序，便于采用贪心策略
- 贪心策略选择
- 方案一：从最快的马开始比较
- 用我方最快的马去比较田忌相应位置的马
- 如果能赢就记一分，继续比下一对
- 如果赢不了就用更慢的马去比
- 重复以上过程，直到比完所有马
- 方案二：从最慢的马开始比较
- 用我方最慢的马去比较田忌最慢的马
- 如果能赢就记一分，双方都换下一匹马
- 如果赢不了就换我方下一匹更快的马
- 方案一：从最快的马开始比较
- 获胜场次统计
- 记录每次获胜的场次
- 最终输出总获胜场次
- 时间复杂度分析：
- 排序需要 $O(N\log N)$ 的时间复杂度
- 方案一需要双重循环，时间复杂度为 $O(N^2)$
- 方案二只需单重循环，时间复杂度为 $O(N)$
- 因此方案二的总体时间复杂度为 $O(N\log N)$，优于方案一
- 空间复杂度分析：
- 需要存储双方马匹速度数组，空间复杂度为 $O(N)$
- 排序可能需要额外 $O(\log N)$ 的栈空间
- 总体空间复杂度为 $O(N)$
本题的难点在于正确理解贪心策略，选择合适的比较方案。从最慢的马开始比较（方案二）不仅代码更简洁，时间复杂度也更优。
示例代码
方法一，用最快的去比较，双层循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <algorithm>
// 定义最大数组长度，题目要求N最大为5*10^4
const int max_n = 5 * 10e4 + 5;
// t_array存储田忌的马匹速度
int t_array[max_n];
// m_array存储我方马匹速度
int m_array[max_n];
int main() {
// 读取输入数据
int n;
std::cin >> n;
// 读入我方马匹速度
for (int i = 0; i < n; i++) {
std::cin >> m_array[i];
}
// 读入田忌马匹速度
for (int i = 0; i < n; i++) {
std::cin >> t_array[i];
}
// 对输入数据进行排序，便于后续比较
// 将我方马匹按速度从小到大排序
std::sort(m_array, m_array + n);
// 将田忌马匹按速度从小到大排序
std::sort(t_array, t_array + n);
// 计算满足条件的数对数量
// count记录获胜场次
int count = 0;
// last_j记录上一次找到的田忌马匹位置
int last_j = n;
// 从后向前遍历 m_array，寻找满足条件的数对
// 采用贪心策略，用我方最快的马去比较
for (int i = n - 1; i >= 0; i--) {
// 从最后一个满足条件的数开始向前遍历 t_array，找到第一个满足条件的数对
// 寻找比我方马匹慢的田忌马匹中最快的一匹
for (int j = last_j - 1; j >= 0; j--) {
// 如果找到一匹比田忌的马快，就可以获胜
if (m_array[i] > t_array[j]) {
count++;
// 更新最后一个满足条件的数的索引，避免重复使用
last_j = j;
break;
}
}
}
// 输出满足条件的数对数量，即最多获胜场次
std::cout << count;
return 0;
}
方法二，从最慢的马开始比较，单层循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
// 定义最大数组长度，题目要求N最大为5*10^4
const int max_n = 5 * 10e4 + 5;
// t_array存储田忌的马匹速度
int t_array[max_n];
// m_array存储我方马匹速度
int m_array[max_n];
int main() {
// 读取马匹数量N
int n;
std::cin >> n;
// 读取我方马匹速度数组
for (int i = 0; i < n; i++) {
std::cin >> m_array[i];
}
// 读取田忌马匹速度数组
for (int i = 0; i < n; i++) {
std::cin >> t_array[i];
}
// 对两方马匹速度进行排序，便于采用贪心策略
std::sort(m_array, m_array + n);
std::sort(t_array, t_array + n);
// count记录获胜场次
int count = 0;
// 采用贪心策略，从最慢的马开始比较
// i遍历我方马匹，j遍历田忌马匹
// 如果我方当前马匹比田忌当前马匹快，就可以获胜一场
for (int i = 0, j = 0; i < n; i++) {
// 如果我方当前马比田忌当前马快，就可以获胜
if (m_array[i] > t_array[j]) {
// 获胜场次加1
count++;
// 田忌下一匹马
j++;
}
// 如果我方马不够快，就跳过这轮，用下一匹更快的马去比
}
// 输出最多获胜场次
std::cout << count;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总
“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
