【GESP】C++五级真题（贪心考点） luogu-B3872 [GESP202309 五级] 巧夺大奖
GESP C++ 2023年9月五级真题，贪心算法考点，难度⭐⭐⭐☆☆。洛谷难度等级普及/提高−
luogu-B3872 [GESP202309 五级] 巧夺大奖
题目要求
题目描述
小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：
游戏分为 $n$ 个时间段，参加者每个时间段可以选择一个小游戏。
游戏中共有 $n$ 个小游戏可供选择。
每个小游戏有规定的时限和奖励。对于第 $i$ 个小游戏，参加者必须在第 $T_i$ 个时间段结束前完成才能得到奖励 $R_i$。
小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个小游戏，才能使得总奖励最高？
输入格式
输入第一行，包含一个正整数 $n$。$n$ 既是游戏时间段的个数，也是小游戏的个数。约定 $1\le n\le500$。
输入第二行，包含 $n$ 个正整数。第 $i$ 个正整数为 $T_i$，即第 $i$ 个小游戏的完成期限。约定 $1\le T_i\le n$。
输入第三行，包含 $n$ 个正整数。第 $i$ 个正整数为 $R_i$，即第 $i$ 个小游戏的完成奖励。约定 $1\le R_i\le 1000$。
输出格式
输出一行，包含一个正整数 $C$，为最高可获得的奖励。
输入输出样例 #1
输入 #1
1
2
3
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
输出 #1
1
230
说明/提示
样例解释 1
$7$ 个时间段可分别安排完成第 4、2、3、1、6、7、5 个小游戏，其中第 4、2、3、1、7 个小游戏在期限内完成。因此，可以获得总计 $40+60+50+70+10=230$ 的奖励。
题目分析
解题思路
贪心策略核心：把“最值钱”的游戏尽可能往后塞，让截止时间更早的游戏也能有位置。
- 先按奖励从高到低排序，保证每次处理当前“最值钱”的游戏。
- 对每个游戏，从它的截止时间 $T_i$ 往前扫描，找到第一个空闲时间段就占住。
为什么“倒着找”？
越靠后的时间段越“稀缺”，先把高奖励游戏往后放，前面的时间段就能留给截止时间更早的游戏，最大化总奖励。 - 若找不到空闲段，则该游戏无法完成，直接放弃。
复杂度
排序 $O(n \log n)$，扫描+占段 $O(n^2)$，总体 $O(n^2)$，$n \le 500$ 完全够用。
示例代码
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
#include <algorithm>
#include <cmath>
#include <iostream>
// 小游戏结构体：记录每个游戏的截止时间段与奖励
struct Game {
int time; // 该游戏必须在第 time 个时间段结束前完成
int reward; // 完成该游戏可获得的奖励
};
// 全局数组：games 存储所有小游戏；game_count 标记某时间段是否已被占用
struct Game games[505];
int game_count[505]; // 0 表示该时间段空闲，1 表示已占用
// 排序比较函数：按 reward 降序，优先处理奖励高的游戏
bool cmp(Game a, Game b) { return a.reward > b.reward; }
int main() {
int n;
std::cin >> n; // 读取时间段（也是游戏）总数
// 读取每个游戏的截止时间
for (int i = 1; i <= n; i++) {
std::cin >> games[i].time;
}
// 读取每个游戏的奖励
for (int i = 1; i <= n; i++) {
std::cin >> games[i].reward;
}
// 按奖励从高到低排序，贪心策略：优先安排奖励高的游戏
std::sort(games + 1, games + n + 1, cmp);
int result = 0; // 记录最终能获得的最大奖励
// 遍历排好序的游戏，尝试将其放入最靠近截止时间的空闲段
for (int i = 1; i <= n; i++) {
// 从该游戏截止时间往前找，找到第一个空闲时间段
// 核心贪心策略：奖励越高越优先安排，但要把游戏尽量往后“塞”
// 从截止时间往前扫，找到第一个空闲时间段就占住，
// 这样前面的时间段能留给截止时间更早的游戏，最大化总奖励。
for (int j = games[i].time; j >= 1; j--) {
if (game_count[j] == 0) { // 找到空闲段
result += games[i].reward; // 累加奖励
game_count[j] = 1; // 标记该时间段已占用
break; // 该游戏安排成功，跳出
}
}
}
std::cout << result; // 输出最高可获得的奖励
return 0;
}
所有代码已上传至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)，考试认证学员交流，互帮互助
