【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

PLAINTEXT

3
1 3 5
2 4 6

输出 #1

PLAINTEXT

输入输出样例 #2

输入 #2

PLAINTEXT

5
10 3 5 8 7
4 6 1 2 9

输出 #2

PLAINTEXT

说明/提示

样例解释 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)$

本题的难点在于正确理解贪心策略，选择合适的比较方案。从最慢的马开始比较（方案二）不仅代码更简洁，时间复杂度也更优。

示例代码

方法一，用最快的去比较，双层循环

CPP

#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;
}

方法二，从最慢的马开始比较，单层循环

CPP

#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;
}

C++ 算法考级专栏

【GESP】C++四级真题 luogu-B3928 [GESP202312 四级] 田忌赛马

luogu-B3928 [GESP202312 四级] 田忌赛马

题目要求

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

题目分析

示例代码

方法一，用最快的去比较，双层循环

方法二，从最慢的马开始比较，单层循环

猜你想读 · 相关文章推荐

【GESP】C++四级真题 luogu-B4041 [GESP202409 四级] 区间排序

【GESP】C++四级真题 luogu-B4068 [GESP202412 四级] Recamán

【GESP】C++四级/五级练习题 luogu-P1223 排队接水

OneCoder (lihongzheshuai)

💬 读者留言与交流