2023年GESP五级巧夺大奖（洛谷B3872题）：贪心算法详解

一、问题理解与算法选择

这道题目要求我们在有限的时间内安排多个游戏任务，每个任务有自己的截止时间和奖励值，目标是获得最大的总奖励。这是一个典型的任务调度问题，我们可以使用贪心算法来解决，优先处理奖励高的任务，同时合理安排时间。

二、完整代码解析（含注释）

#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); // 记录时间段是否被占用
    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;
}

三、算法核心思想

1. 贪心策略：优先处理奖励高的任务，这样可以确保高奖励任务优先获得时间安排

2. 时间安排：为每个任务从它的截止时间开始向前寻找第一个空闲时间段

3. 数据结构：使用布尔数组slot记录每个时间段是否被占用

四、关键步骤详解

1. 输入处理：

• 读取游戏任务数量n

• 分别读取每个任务的截止时间和奖励值

• 将任务存储在结构体数组中

2. 任务排序：

• 使用自定义比较函数compareReward

• 按奖励值从高到低排序，确保高奖励任务优先处理

3. 时间分配：

• 初始化时间段标记数组slot，记录每个时间段是否被占用

• 对于每个任务，从它的截止时间开始向前寻找第一个空闲时间段

• 找到后标记该时间段为已占用，并累加奖励值

4. 结果输出：

• 输出能够获得的最大总奖励

五、常见问题解答

Q: 为什么使用贪心算法？ A: 因为我们需要最大化总奖励，优先处理高奖励任务可以保证局部最优，进而达到全局最优。

Q: 如何处理任务截止时间超过n的情况？ A: 使用min(n, games[i].deadline)确保不会越界。

Q: 为什么时间要从截止时间往前找？ A: 这样可以最大化利用时间资源，给后面的任务留出更多选择空间。