【CSP】CSP-XL 2025辽宁复赛真题-第三题, 小L打比赛（match）

CSP-XL 2025辽宁复赛真题-第三题，小L打比赛（match），贪心思想考点，个人认为约相当于GESP四级+，五级-，难度⭐⭐★☆☆。

CSP-XL 2025辽宁复赛真题-第三题, 小L打比赛（match）

题目要求

---

题目分析

解题思路

1. 题意再述
   小 L 有 $n$ 场比赛，第 $i$ 场开始时间为 $s_i$，结束时间为 $e_i$（时间均为整数分钟）。
   他一旦参加某场比赛就必须完整打完，不能中途加入或退出；且任意两场比赛不能重叠（即前一场结束时间必须严格小于后一场开始时间）。
   目标：在以上规则下，最多能完整参加多少场比赛。

2. 贪心核心——“结束时间最早”策略
   直觉：越早结束的比赛，留给后面可选的“剩余时间”越多。
   证明（交换论证）：
   假设最优解中第一场结束时间不是全局最早结束的，那把第一场替换成结束时间最早且与之兼容的比赛，不会减少后续可选场次，反而可能腾出更多时间。因此“结束最早”策略不会比任何最优解差，故其本身就是最优。

   算法步骤：
   ① 把所有比赛按结束时间 $e_i$ 升序排序；
   ② 用变量 cur_end 记录已选的最后一场的结束时间；
   ③ 顺序扫描排序后的列表，若当前比赛开始时间 $s_i \gt$ cur_end，则选中该场，更新 cur_end $= e_i$，计数器 count++；
   ④ 扫描完毕，count 即为答案。

3. 复杂度
   • 时间：排序 $O(n\log n)$，贪心扫描 $O(n)$，总体 $O(n\log n)$。
   • 空间：仅用到常数级额外变量。
4. 实现细节
   • 结构体存 (start, end)，用 std::sort 自定义比较函数 cmp(a,b){return a.end<b.end;}。
   • 文件读写按复赛要求用 freopen。

---

示例代码

#include <algorithm>
#include <iostream>

struct Match {
    int start = 0; // 比赛开始时间
    int end = 0;   // 比赛结束时间
};

// 按结束时间升序排序的比较函数
bool cmp(Match a, Match b) { return a.end < b.end; }

// 全局数组，存储所有比赛
struct Match matches[500005];

int main() {
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    int n;
    std::cin >> n;
    // 读入 n 场比赛的起止时间
    for (int i = 0; i < n; i++) {
        std::cin >> matches[i].start >> matches[i].end;
    }
    // 按结束时间升序排序，为贪心选择做准备
    std::sort(matches, matches + n, cmp);
    int count = 1;              // 至少能打一场比赛
    int cur_end = matches[0].end; // 当前所选最后一场的结束时间

    // 贪心选择：每次挑结束时间最早且不与上一场比赛冲突的比赛
    for (int i = 1; i < n; i++) {
        if (matches[i].start > cur_end) { // 无冲突
            count++;
            cur_end = matches[i].end;     // 更新最后结束时间
        }
    }
    std::cout << count << std::endl; // 输出最多能观看的比赛场数
    return 0;
}

---

附：样例和测试数据下载地址：

链接：https://pan.quark.cn/s/83ce9a16c3fc?pwd=kjYS 提取码：kjYS

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号