GESP五级题巧夺大奖解题报告：贪心算法优化与代码实现（洛谷B3872）
2个月前 (06-27)
一、题目解读
2023年GESP五级题目“巧夺大奖”（洛谷B3872）是一个经典的资源分配问题。题目要求玩家在有限时间内选择多个游戏，每个游戏有截止时间和奖励值，需在截止时间前完成游戏以获得奖励。目标是通过策略选择，最大化总奖励。问题关键在于如何在时间冲突的情况下合理分配任务，属于典型的贪心算法应用场景。
二、解题思路
采用贪心策略：优先选择奖励高的游戏，并为其分配最早可用的时间段。核心思想是“优先满足高价值任务”，通过以下步骤实现：
1. 奖励降序排序：按游戏奖励从高到低排序，确保优先处理高收益任务。
2. 逆序查找可用时段：从每个游戏的截止时间逆向遍历时间段，找到第一个未被占用的槽位并标记，避免时间冲突。
该策略保证在有限时间内优先选择高奖励任务，降低因低奖励任务占用资源导致总收益下降的风险。
三、解题步骤
1. 输入数据：读取游戏数量n，依次输入各游戏的截止时间和奖励值。
2. 数据预处理：对游戏数组按奖励降序排序。
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)避免越界）。此策略为同类资源分配问题提供了经典范式，值得深入理解。
原创内容 转载请注明出处
