一、题目解读2023年GESP五级题目“巧夺大奖”（洛谷B3872）是一个经典的资源分配问题。题目要求玩家在有限时间内选择多个游戏，每个游戏有截止时间和奖励值，需在截止时间前完成游戏以获得奖励。目标是通过策略选择，**化总奖励。问题关键在于如何在时间冲突的情况下合理分配任务，属于典型的贪心算法应用场景。 二、解题思路采用贪心策略：优先选择奖励高的游戏，并为其分配最早可用的时间段。核心思想是“优先满足高价值任务”，通过以下步骤实现： 1. 奖励降序排序：按游戏奖励从高到低排序，确保优先处理高收益任务。 2. 逆序查找可用时段：从每个游戏的截止时间逆向遍历时间段，找到**个未被占用的槽位并标记，避免时间冲突。 该策略保证在有限时间内优先选择高奖励任务，降低因低奖励任务占用资源导致总收益下降的风险。 三、解题步骤1. 输入数据：读取游戏数量n，依次输入各游戏的截止时间和奖励值。 3. 分配时间段： 遍历每个游戏，从截止时间开始逆向遍历时间段（1到min(n, deadline)）。 若找到未被占用的时段（slot[j]为false），标记该时段并累加奖励，跳出循环。 4. 输出结果：最终累加的奖励总值即为**解。 四、代码与注释
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct Game {
- int deadline; // 截止时间
- int reward; // 奖励值
- };
- // 按奖励降序排序的比较函数
- bool compareReward(const Game& a, const Game& b) {
- return a.reward > b.reward;
- }
- int main() {
- int n; // 游戏数量
- cin >> n;
-
- vector<Game> games(n); // 存储游戏信息
- for (int i = 0; i < n; ++i) {
- cin >> games[i].deadline;
- }
- for (int i = 0; i < n; ++i) {
- cin >> games[i].reward;
- }
-
- // 贪心核心：按奖励降序排序
- sort(games.begin(), games.end(), compareReward);
-
- vector<bool> slot(n + 1, false); // 时间段占用标记（1~n）
- int total = 0; // 总奖励
-
- // 分配时间段
- for (int i = 0; i < n; ++i) {
- for (int j = min(n, games[i].deadline); j >= 1; --j) {
- if (!slot[j]) { // 找到可用时段
- slot[j] = true;
- total += games[i].reward;
- break; // 当前游戏分配完毕
- }
- }
- }
-
- cout << total << endl;
- return 0;
- }
五、总结该解法通过贪心算法实现高效求解，时间复杂度为O(nlogn)（排序）+ O(n²)（分配），但实际由于逆序查找的优化，常表现出接近线性效率。关键在于“高奖励优先”的排序和“逆向查找空位”的分配逻辑，避免了复杂的动态规划，适用于大规模数据场景。需注意边界处理（如min(n, deadline)避免越界）。此策略为同类资源分配问题提供了经典范式，值得深入理解。
| 
发表于 