P4789 勇敢者游戏（提高）

解题思路

第一步，读懂题目。 比赛一开始奖励童童 m 元。比赛有 n 个时段，还有 n 个小游戏，每个游戏 i 必须在期限 t_i 前完成（一个时段只能做一个游戏），没按时完成的游戏要扣 w_i 元。问童童最多能赢多少钱。

第二步，把目标转一下。 一开始有 m 元，赢的钱 = m 减去被扣掉的钱。被扣得越少，赢的越多。所以我们要尽量把扣款多的游戏都做完，让扣款大的游戏不被扣钱。

第三步，确定贪心策略。 把所有游戏按扣款 w_i 从大到小排序，优先安排扣款多的游戏。安排游戏 i 时，从它的期限 t_i 开始往前找最后一个空闲的时段，把它放在那里；如果期限前的所有时段都满了，这个游戏就完不成，把它的扣款记下来。

第四步，为什么从后往前找？ 每个游戏只要在期限内完成就行，没有规定必须早做。把游戏尽量放得晚，就能把前面紧张的时段留给期限更紧、更需要早做的游戏。就像交作业，期限前交都算数，尽量往后拖，把前面的时间留给更急的作业。

第五步，处理期限超过 n 的情况。 比赛总共只有 n 个时段，所以如果某个游戏的期限大于 n，就把它当成 n 来处理，因为超过 n 的时段根本不存在。

第六步，举一个例子。 m=10000，7 个游戏。按扣款从大到小安排，扣 70、60、50、40 的游戏都顺利安排上了；扣 30、20 的两个游戏找不到空闲时段，被扣掉 30+20=50 元；扣 10 的游戏期限 6 还有位置，安排上。所以最多赢 10000-50=9950 元。

参考代码

// 勇敢者游戏：扣款越多的游戏越优先安排，每个游戏尽量放在期限前的最后一个空闲时段，没安排上的才扣钱
#include <iostream>
#include <algorithm>
using namespace std;

struct Game {
    int deadline; // 规定完成期限
    int penalty;  // 没按时完成的扣款
};

Game games[100005];

// 比较函数：扣款多的游戏排在前面，优先安排
bool cmp(const Game &a, const Game &b) {
    return a.penalty > b.penalty;
}

bool occupied[100005];

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &games[i].deadline);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &games[i].penalty);
    }
    sort(games, games + n, cmp);
    long long lost = 0; // 被扣掉的总钱数
    for (int i = 0; i < n; i++) {
        // 期限如果比总时段 n 还大，就按 n 算，因为最多只有 n 个时段
        int deadline = games[i].deadline;
        if (deadline > n) deadline = n;
        bool placed = false;
        // 从期限往前找最后一个空闲的时段来安排这个游戏
        for (int slot = deadline; slot >= 1; slot--) {
            if (!occupied[slot]) {
                occupied[slot] = true;
                placed = true;
                break;
            }
        }
        // 找不到空闲时段，这个游戏完不成，要被扣钱
        if (!placed) {
            lost += games[i].penalty;
        }
    }
    printf("%lld\n", m - lost);
    return 0;
}

复杂度分析

排序需要 O(n log n)。安排每个游戏时，最坏要从期限一直往前找空闲时段，最多找 n 个，所以最坏情况总时间复杂度是 O(n 的平方)。空间 O(n)，用一个布尔数组记录每个时段是否被占用。