n 个时间段、n 个小游戏,每个游戏有截止期限与奖励,求最大总奖励。
游戏分 n 个时间段,共有 n 个小游戏。第 i 个游戏必须在第 Tᵢ 个时间段结束前完成,完成后获得奖励 Rᵢ。每个时间段只能做一个小游戏。
求能获得的最大总奖励。
贪心截止期限调度空位分配按价值排序
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 Tᵢ;第三行 Rᵢ |
| 输出 | 最大总奖励 |
| 数据范围 | 1 ≤ n ≤ 500 |
| 期限 | 1 ≤ Tᵢ ≤ n |
| 奖励 | 1 ≤ Rᵢ ≤ 1000 |
截止期 T = [4, 2, 4, 3, 1, 4, 6],奖励 R = [70, 60, 50, 40, 30, 20, 10]。
游戏 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 降序
游戏 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 | 游戏 4 | 3 | 40 |
| 2 | 游戏 2 | 2 | 60 |
| 3 | 游戏 3 | 4 | 50 |
| 4 | 游戏 1 | 4 | 70 |
| 5 | 游戏 7 | 6 | 10 |
| 6 | (空) | — | 0 |
| 7 | (空) | — | 0 |
40 + 60 + 50 + 70 + 10 = 230 ✓
用一个交换论证来说明。
某个最优方案里,把游戏 A(期限 T_A)放在了较早的 s 号位,而较晚的 t 号位(s < t ≤ T_A)放了游戏 B 或空着
可以改进
把 A 移到 t 号位(仍然满足 t ≤ T_A)
A 的完成时间变晚但仍在期限内 ✓
如果 t 号位原本是空的,直接移过去,没损失
如果是游戏 B,把 B 移到 s 号位
B 会受影响吗?
B 从 t 移到 s(更早),完成时间提前
提前完成当然仍在期限内 ✓
所以交换后两个游戏都合法,总奖励不变
说明"尽量往后放"不会更差
✅ 得证
奖励降序,每个游戏放到 ≤ Tᵢ 的最晚空位
used[1..n] 标记时间段占用;对每个游戏从 min(T[i], n) 往前找第一个未占位置。还可以用并查集把找空位加速到近似 O(1)(本题不需要)。枚举每个时间段选哪个游戏,回溯搜索最大值
| 方案 | 复杂度(n = 500) | 可行性 |
|---|---|---|
| 贪心 + 最晚空位 | 约 2.5 × 10⁵ | ✅ 瞬间 |
| 回溯搜索 | 指数级 | ❌ 不可行 |
第一行输入 n,第二行输入截止期 T,第三行输入奖励 R。
点按钮开始 →
#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) 的边界;④ 安排不上时没跳过,仍然累加奖励。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
7 | 230 | 题面样例 |
1 | 5 | 只有一个游戏,直接做 |
2 | 20 | 两个游戏都只能放第 1 段,只能选奖励高的 |
3 | 15 | 期限刚好递增,三个都能安排 |
3 | 3 | 三个都只能在前 3 段,共 3 段刚好全安排 |
一个长度为 n + 1 的占用标记数组。
✅ 约 25 万次操作,瞬间完成。如果需要 n 达 10⁵,可以用并查集把找空位优化到近似 O(1)。
// 带截止期的任务调度贪心模板 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 很大时加速 |