GESP五级题巧夺大奖解题报告：贪心算法优化与代码实现（洛谷B3872）

一、题目解读

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)避免越界）。此策略为同类资源分配问题提供了经典范式，值得深入理解。