记录一道 GESP 2023年9月 的贪心真题。这类题在考试里属于必得分项，核心就那几行代码，关键是别在小细节上丢分。
题目来源：ACGO A83120 ｜ 2023年9月 五级
赛事场次：2023年9月 五级
一、题目信息
题目名称：巧夺大奖
赛事场次：2023年9月 五级
难度定位：五级
涉及知识点：贪心
题目链接：https://www.acgo.cn/problemset/info/83120
坑点（这题失分基本都在这）
- 局部最优的选取依据；正确性的证明思路（反证法/交换论证）。
题意简述
小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：
1 、游戏分为 n 个时间段，参加者每个时间段可以选择一个小游戏。
2 、游戏中共有 n 个小游戏可供选择。
3 、每个小游戏有规定的时限和奖励。对于第 i 个小游戏，参加者必须在第 Tᵢ 个时间段结束前完成才能得到奖励 Rᵢ 。
小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个小游戏，才能使得总奖励最高？
前置知识
下面先把需要的基础知识理一遍，不熟悉的朋友可以跟着看，熟悉的直接跳过。
贪心的前提：每一步都选当前看起来最优的方案，但必须能证明这样能得到全局最优，否则要换成其他方法。
二、思路分析
先看清楚题目要我们做什么
把题目读两遍，我们提取出关键信息：输入是什么、要输出什么、有哪些约束条件。这道题考查的是贪心，属于这类题里比较基础的一道，把题目要求一步步翻译成代码逻辑就能解决。
我的思考过程
读完题之后，我的第一反应是这样的：注释解析：
顺着这个方向往下想，就得到完整做法：
- 结构体 game_t 存储每个小游戏的完成期限和奖励。
- 比较函数 game_cmp 用于按照奖励降序排列小游戏。
- 布尔数组 arrange 记录每个时间段是否已经安排了小游戏。
- 主函数中使用贪心算法，按照奖励降序排列小游戏，并在每个时间段选择奖励最高的未安排小游戏。
需要说明的是，上面这个思路是把题目要求直译成代码得到的，没有用到什么高级技巧。对于这类基础题，读准题意加写对边界比追求巧妙解法更重要，因为考试里这种题是必须拿满分的。
三、完整代码 + 逐行注释
#include <iostream> #include <algorithm> using namespace std; int n = 0; // 初始化 struct game_t { int T, R; // T表示完成期限，R表示奖励 } games[500]; // 定义一个比较函数，按照奖励降序排列 bool game_cmp(game_t x, game_t y) { return x.R > y.R; } bool arrange[500]; // 记录每个时间段是否已经安排了小游戏 int main() { cin >> n; // 读入 for (int i = 0; i < n; i++) // 遍历 arrange[i] = false; // 输入每个小游戏的完成期限 for (int i = 0; i < n; i++) // 遍历 cin >> games[i].T; // 读入 // 输入每个小游戏的奖励 for (int i = 0; i < n; i++) // 遍历 cin >> games[i].R; // 读入 // 按照奖励降序排列小游戏 sort(games, games + n, game_cmp); int sum = 0; // 初始化 // 遍历每个小游戏 for (int i = 0; i < n; i++) { // 遍历 // 从小游戏的完成期限开始往前遍历时间段 for (int t = games[i].T - 1; t >= 0; t--) { // 遍历 // 找到第一个未安排小游戏的时间段，将该小游戏安排在这个时间段，并累加奖励 if (!arrange[t]) { // 判断 arrange[t] = true; sum += games[i].R; break; } } } // 输出最终的总奖励 cout << sum << endl; // 输出 return 0; }四、代码分段拆解
为了看得更清楚，我们把代码按功能分成几段解释。
第一步：引入头文件
#include <iostream> #include <algorithm> using namespace std;#include <iostream>提供输入输出功能，using namespace std;让我们能直接写cin、cout而不用加前缀。这两行是几乎所有 C++ 程序的开头，照写即可。
第二步：读入数据
cin >> n; cin >> games[i].T; cin >> games[i].R;注意变量的类型要能装下题目的数据。数据可能超过 21 亿时要改用long long。
第三步：核心处理逻辑
for (int i = 0; i < n; i++) for (int i = 0; i < n; i++) for (int i = 0; i < n; i++) for (int i = 0; i < n; i++) {这一段是整道题的关键，也是贪心的体现。看循环的三个要素：从哪里开始、什么时候结束、每次怎么变化。这三个要素任何一个写错，结果都会不对。
第四步：按要求输出
cout << sum << endl;输出格式必须和题目要求的完全一致。很多同学算法完全正确却因为少了一个换行或者空格多寡不对而 WA，这种分丢得最可惜。
五、实例模拟
光看代码可能还不够直观，我们用题目的样例实际跑一遍，看看程序是怎么走的。
以题目的第一组样例为例：
样例输入
7 4 2 4 3 1 4 6 70 60 50 40 30 20 10样例输出
230把这份输入代进代码，程序会先把数据依次读入，然后进入循环逐个判断，把满足条件的值累积起来，最后按格式输出。建议你对照着代码在纸上走一遍前两次循环，确认自己对每一步的理解都和程序一致。
六、踩坑总结
下面是做这道题时最容易出错的地方，对照自己的代码检查一下：
- 变量类型选错：虽然本题范围不大，但养成习惯——凡是不确定范围时，累加变量一律用
long long，成本为零但能保命。 - 输出格式不符：题目要求输出几行就输出几行，行末换行、数字之间的空格都要严格对齐，算法对了但格式错了同样判 WA，这种分丢得最冤。
- 特殊情况没特判：把最小数据、最大数据、答案恰好等于 0 的情况各测一遍。特别是边界输入，出题人最喜欢在这里设陷阱。
七、知识点拓展
最后总结一下这道题带给我们的通用经验：
- 本题考查贪心的基本写法，这类题在考试中属于必得分项，要练到能默写。
- 写完代码后建议自己造几组边界数据测试，特别是最小值和最大值。
- 同一知识点在不同场次反复出现，把这道题的写法吃透，后面遇到同类题可以直接套用。
八、适用人群
如果你已经掌握贪心的基本写法，这道题可以用来巩固手感。
这道题就讲到这里。我会持续更新各场次真题的详细拆解，需要系统复习的同学可以关注这个系列。有问题欢迎评论区讨论。
