GESP 题解库 / 5 级题解 / [GESP202309 五级] 巧夺大奖 · 第 17 / 23 题
GESP202309 五级 · B3872 · 中等

巧夺大奖

n 个时间段、n 个小游戏,每个游戏有截止期限与奖励,求最大总奖励。

📊
n ≤ 500
数据规模
🔢
int
数值类型
⚡
O(n²)
时间复杂度
🎯
按奖励贪心 + 最晚空位
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

游戏分 n 个时间段,共有 n 个小游戏。第 i 个游戏必须在第 Tᵢ 个时间段结束前完成,完成后获得奖励 Rᵢ。每个时间段只能做一个小游戏。

求能获得的最大总奖励。

💡
人话翻译:典型的"任务调度 + 截止期限"贪心模型。策略是:按奖励从高到低处理每个游戏,每个游戏尽量安排在不超过它截止期限的最晚空位上。
"越贵越先安排、能拖就往后拖"——把前面的空位留给截止期更紧的游戏。

🔍 关键词提取

贪心截止期限调度空位分配按价值排序

已知条件

项目说明
输入第一行 n;第二行 Tᵢ;第三行 Rᵢ
输出最大总奖励
数据范围1 ≤ n ≤ 500
期限1 ≤ Tᵢ ≤ n
奖励1 ≤ Rᵢ ≤ 1000

需要解决的问题

02
思维导图
整理解题思路的全貌
🏆 按奖励降序 + 最晚空位
📊 预处理
把游戏按奖励降序排列
每个游戏带截止期 Tᵢ
用一个数组标记时间段是否被占
时间段编号 1 ~ n
🔁 逐个安排
取当前奖励最大的游戏
从 min(Tᵢ, n) 往前找空位
找到就占用并累加奖励
找不到就放弃
🧠 为什么对
贵的游戏优先保证
能拖就拖,保留前面的空位
前面的空位对"期限紧"的游戏更宝贵
交换论证可证最优
⚠️ 易错点
按奖励升序(反了)
放在"最早空位"(会挤掉别人)
忘记 Tᵢ 可能超过 n
没有跳过安排不上的游戏
03
样例手算推导
样例的完整调度过程

🧮 样例:n = 7

截止期 T = [4, 2, 4, 3, 1, 4, 6],奖励 R = [70, 60, 50, 40, 30, 20, 10]。

1
第 1 步:按奖励降序排列

游戏 1:T=4,R=70

游戏 2:T=2,R=60

游戏 3:T=4,R=50

游戏 4:T=3,R=40

游戏 5:T=1,R=30

游戏 6:T=4,R=20

游戏 7:T=6,R=10

已按 R 降序

2
第 2 步:逐个安排

游戏 1(T=4):4 号位空闲 → 占 4 号,+70

游戏 2(T=2):2 号位空闲 → 占 2 号,+60

游戏 3(T=4):≤4 的最晚空位是 3 号 → 占 3 号,+50

游戏 4(T=3):≤3 的空位只剩 1 号 → 占 1 号,+40

游戏 5(T=1):≤1 的空位全被占 → 放弃

游戏 6(T=4):≤4 的 1~4 号全被占 → 放弃

游戏 7(T=6):≤6 的最晚空位是 5 号 → 占 5 号,+10

✅ 总计 230

📊 时间段的最终安排

时间段安排的游戏该游戏期限获得奖励
1游戏 4340
2游戏 2260
3游戏 3450
4游戏 1470
5游戏 7610
6(空)—0
7(空)—0

40 + 60 + 50 + 70 + 10 = 230 ✓

🔑
为什么游戏 4 放在 1 号位而不是 3 号位?因为 3 号位、4 号位已经被更贵的游戏占了。游戏 4 的期限是 3,所以在 ≤3 的范围里能用的最晚位置是 1 号(2、3 已占)。注意"最晚空位"是"在已占情况下能找到的最晚位置",而不是"Tᵢ 本身"。

🧮 为什么"能拖就拖"是最优的

用一个交换论证来说明。

1
假设反例

某个最优方案里,把游戏 A(期限 T_A)放在了较早的 s 号位,而较晚的 t 号位(s < t ≤ T_A)放了游戏 B 或空着

可以改进

2
交换一下

把 A 移到 t 号位(仍然满足 t ≤ T_A)

A 的完成时间变晚但仍在期限内 ✓

如果 t 号位原本是空的,直接移过去,没损失

如果是游戏 B,把 B 移到 s 号位

B 会受影响吗?

3
B 是否仍合法

B 从 t 移到 s(更早),完成时间提前

提前完成当然仍在期限内 ✓

所以交换后两个游戏都合法,总奖励不变

说明"尽量往后放"不会更差

✅ 得证

⚠️
这就是"贪心 + 交换论证"的典型套路:先猜测一个贪心策略,再用"交换任意两个元素不会变差"来证明它最优。写题解时能说清这个道理,比只背模板有价值得多。
04
解法对比
贪心安排 vs 状压/回溯搜索

⚔️ 解法对比

🟢 按奖励贪心 + 最晚空位(推荐) 推荐

奖励降序,每个游戏放到 ≤ Tᵢ 的最晚空位

  • 时间 O(n²)
  • n = 500 时约 25 万次
  • 代码 20 行
  • 有交换论证支撑
💡
实现:used[1..n] 标记时间段占用;对每个游戏从 min(T[i], n) 往前找第一个未占位置。还可以用并查集把找空位加速到近似 O(1)(本题不需要)。

🟠 状压 / 回溯搜索

枚举每个时间段选哪个游戏,回溯搜索最大值

  • 复杂度指数级或 O(n!)
  • n = 500 完全不可行
  • 只能处理 n ≤ 15 左右的规模
  • 不适合本题
⚠️
注意:本题 n 可达 500,搜索类做法根本不可能。而且这类"带截止期的任务选择"问题有确定的贪心最优解,不需要搜索。

📈 性能对比

方案复杂度(n = 500)可行性
贪心 + 最晚空位约 2.5 × 10⁵✅ 瞬间
回溯搜索指数级❌ 不可行
05
算法流程图
排序后逐个安排到最晚空位
开始读入 n、数组 T、R;把游戏按 R 降序排列ans = 0;used[1..n] 全部标记为空依次处理每个游戏j = min(T[i], n),从 j 往前找第一个空位找到空位了吗?是 ✓占用该位置,ans += R[i]否 ✗放弃这个游戏所有游戏都处理完后输出 ans结束处理下一个游戏
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🏆 最优调度计算器

第一行输入 n,第二行输入截止期 T,第三行输入奖励 R。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

struct Game { int t, r, id; };

int main() {
    int n;
    scanf("%d", &n);

    vector<Game> g(n);
    for (int i = 0; i < n; i++) { scanf("%d", &g[i].t); g[i].id = i + 1; }
    for (int i = 0; i < n; i++) scanf("%d", &g[i].r);

    // 按奖励从高到低排序
    sort(g.begin(), g.end(), [](const Game &a, const Game &b) {
        return a.r > b.r;
    });

    vector<bool> used(n + 1, false);      // 时间段 1 ~ n
    int ans = 0;

    for (int i = 0; i < n; i++) {
        // 从 min(t, n) 往前找第一个空位
        int j = min(g[i].t, n);
        while (j >= 1 && used[j]) j--;

        if (j >= 1) {                     // 找到空位就安排
            used[j] = true;
            ans += g[i].r;
        }
        // 找不到就放弃这个游戏
    }

    printf("%d\n", ans);
    return 0;
}
🔑
为什么循环上界写 min(t, n)?虽然题目保证 Tᵢ ≤ n,但养成"取 min"的习惯更安全——万一数据超出预期也不会数组越界。而搜索方向是从后往前,正是为了实现"能拖就拖"。

📖 关键几行怎么看

代码作用为什么这样写
a.r > b.r降序排序贵的游戏优先安排
int j = min(g[i].t, n)起始位置从期限处开始往前找
while (j >= 1 && used[j]) j--;找最晚空位越晚放越好,给前面的游戏让位
if (j >= 1) { ... }安排或放弃找不到空位就跳过,不加奖励
⚠️
四个坑:① 按奖励升序排序(方向反了);② 从前往后找最早空位(会挤掉期限紧的游戏);③ 忘记 min(T[i], n) 的边界;④ 安排不上时没跳过,仍然累加奖励。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
230题面样例
1
1
5
5只有一个游戏,直接做
2
1 1
10 20
20两个游戏都只能放第 1 段,只能选奖励高的
3
1 2 3
5 5 5
15期限刚好递增,三个都能安排
3
3 3 3
1 2 3
3三个都只能在前 3 段,共 3 段刚好全安排
✅
自查清单:① 降序排序了吗?② 从后往前找空位吗?③ 放不下时跳过了吗?

🚨 易错点清单

⚠️
排序方向反了:必须按奖励降序,让贵的游戏优先。
⚠️
找"最早空位":应该从期限处往前找最晚空位,否则会挤掉期限更紧的游戏。
⚠️
安排不上仍累加:找不到空位时要跳过,不能加奖励。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²)
空间复杂度
O(n)
n 最大
500
运算量
约 2.5 × 10⁵

时间怎么算的?

空间都用在哪?

一个长度为 n + 1 的占用标记数组。

✅ 约 25 万次操作,瞬间完成。如果需要 n 达 10⁵,可以用并查集把找空位优化到近似 O(1)。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 带截止期的任务调度贪心模板
sort(tasks.begin(), tasks.end(), [](const A &a, const A &b){ return a.value > b.value; });
vector<bool> used(n + 1, false);
long long ans = 0;
for (auto &task : tasks) {
    int j = min(task.deadline, n);
    while (j >= 1 && used[j]) j--;
    if (j >= 1) { used[j] = true; ans += task.value; }
}

// 用并查集优化找空位(n 很大时)
// fa[i] 表示"从 i 往前第一个可用位置的候选"
int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }
int j = find(min(task.deadline, n));
if (j >= 1) { used[j] = true; ans += task.value; fa[j] = find(j - 1); }

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
截止期贪心按价值降序 + 最晚空位任务调度、作业安排、打折券使用
交换论证证明贪心不会更差所有需要证明贪心正确性的场合
并查集优化空位近似 O(1) 找空位n 很大时加速
🌟
思考题:如果题目改成"每个游戏需要连续两个时间段才能完成",贪心还成立吗?(提示:不再直接成立——因为"占一个位置"变成了"占一段区间",交换论证会变得复杂,需要改成"按价值降序,找最晚的、能容纳两个连续空段的区间"。这说明贪心策略对"资源占用方式"的改变很敏感。)