你好！我是你的OI教练。今天我们来攻克 GESP 2023年9月 五级真题 B3872《巧夺大奖》。

这是一道非常经典的贪心算法题目，在算法竞赛中常被称为“带截止期限的作业调度问题”（Job Sequencing Problem with Deadlines）。它不像前面的题目那样只要算算数，这道题需要你像一个精明的“时间管理大师”一样做决策。

---

1. 读题关键词：你的“雷达”响了吗？

读题时，请圈出以下几个决定代码逻辑的关键信息：

1. “$n$ 个时间段”、“每个时间段选择一个小游戏”：
   • 这意味着你的资源（时间）是有限的，只有 $1, 2, \dots, n$ 这几个坑位。
   • 每个游戏耗时 1 个时间段。
2. “截止期限 $T_i$” 和 “奖励 $R_i$”：
   • 这是每个任务的两个属性。
   • 关键点：要想拿到奖励 $R_i$，必须在时刻 $T_i$ 或之前 完成。
   • 陷阱：在 $T_i$ 之前完成也可以！比如 $T_i=3$，你在第 1、2、3 个时间段做都可以。
3. 目标：“总奖励最高”：
   • 典型的最优化问题。看到“最大/最小”，优先想贪心或DP。这里数据模型比较简单，大概率是贪心。

---

2. 预备知识点

要解决这道题，你需要掌握：

• 结构体 (struct)：把每个游戏的 $R$ 和 $T$ 打包在一起。
• 排序 (sort)：贪心的核心，决定我们先考虑哪个游戏。
• 标记数组 (bool array)：用来记录哪个时间段已经被占用了。

---

3. 启发式教学：草稿纸上的推演

来，我们在草稿纸上画一画。 假设我们有 3 个游戏，时间段只有 3 个。

游戏ID	奖励 ($R$)	截止期限 ($T$)
A	100	2
B	50	1
C	10	2

策略一：按截止时间早晚做？（先做着急的）

• 先做 B (期限1)，占用时间段 1。
• 再做 A (期限2)，占用时间段 2。
• C (期限2) 没地方放了。
• 总分：$50 + 100 = 150$。
• 看起来不错？但如果 B 的奖励只有 1 分呢？你会为了捡芝麻丢西瓜吗？

策略二：按奖励多少做？（先做值钱的）—— 正解思路

• 第一步：我最想要 A (100分)。
  • 它期限是 2。
  • 思考：我应该把它安排在时间段 1 还是 时间段 2？
  • 贪心策略：好饭不怕晚，占坑要占边。如果我把它安排在 1，可能会挤占掉那些“必须在1完成”的游戏。如果我把它安排在 2（最后期限），就给前面的游戏留出了空位。
  • 决策：把 A 安排在时间段 2。
• 第二步：我想要 B (50分)。
  • 它期限是 1。时间段 1 是空的吗？是。
  • 决策：把 B 安排在时间段 1。
• 第三步：我想要 C (10分)。
  • 它期限是 2。
  • 检查时间段 2：被 A 占了。
  • 检查时间段 1：被 B 占了。
  • 决策：没地儿了，放弃 C。
• 总分：$100 + 50 = 150$。

核心贪心策略总结：

1. 贪婪：优先考虑奖励最高的游戏。
2. 谦让：对于选中的游戏，在它允许的范围内，尽量往后排（尽量靠近截止期限 $T_i$）。为什么？因为越晚的时间段越“不值钱”（能用晚的时间段的游戏，通常也能用早的；但只能用早的时间段的游戏，用不了晚的）。留着前面的时间段给那些“腿短”的游戏用。

---

4. 详细解题步骤

1. 存储：用结构体数组存所有游戏。
2. 排序：按奖励 $R$ 从大到小排序。如果奖励相同，按期限排序（其实无所谓）。
3. 占位：准备一个 bool used[N+1] 数组，初始化为 false，表示时间段 1 到 $n$ 都没被占用。
4. 遍历：
   • 拿出当前奖励最大的游戏，设期限为 $t$。
   • 从 $t$ 开始往回找（$t, t-1, t-2, \dots, 1$）。
   • 找到第一个没被占用的时间段 $k$。
   • 如果找到了：标记 used[k] = true，总分加上该奖励。
   • 如果找到 1 还没空位：说明这个游戏插不进去了，放弃。

---

5. 标准代码 (NOIP C++14)

注意：根据 GESP 常见的输入风格，输入格式可能是 $N$ 行数据，也可能是三行（先N，再一行R，再一行T）。下面的代码演示了处理三行输入的情况（根据洛谷题目反馈）。如果是 $N$ 行，修改输入部分即可。

提醒：下面这个代码版本的错误的,错误原因见后面解释：

/**
 * 题目：B3872 [GESP202309 五级] 巧夺大奖
 * 考点：贪心算法、结构体排序
 * 时间复杂度：O(N^2) —— N <= 500 时完全没问题
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 1. 定义游戏结构体
struct Game {
    int id;
    int r; // 奖励 Reward
    int t; // 截止期限 Time Limit
};

// 2. 排序规则：奖励高的排前面
bool cmp(const Game &a, const Game &b) {
    // 只要奖励大就在前
    // 如果奖励相同，谁在前无所谓，不影响结果
    return a.r > b.r;
}

// 记录时间段是否被占用 (根据题目N范围，设大一点)
bool used[1005]; 

void solve() {
    int n;
    cin >> n; // 读取游戏数量

    vector<Game> games(n);

    // 注意：有些题目是先输入所有R，再输入所有T
    // 根据洛谷/GESP真题常见格式，这里按"三行流"处理
    // 第二行：输入所有奖励
    for (int i = 0; i < n; i++) {
        cin >> games[i].r;
        games[i].id = i;
    }
    // 第三行：输入所有期限
    for (int i = 0; i < n; i++) {
        cin >> games[i].t;
    }
    
    // 如果输入格式是 N 行 (R T)，请把上面两个循环合并为：
    // for(int i=0; i<n; i++) cin >> games[i].r >> games[i].t;

    // 3. 贪心第一步：排序
    sort(games.begin(), games.end(), cmp);

    // 初始化时间段占用情况
    for (int i = 0; i <= n; i++) used[i] = false;

    long long totalReward = 0; // 总分可能很大，用 long long 是好习惯

    // 4. 贪心第二步：从大到小尝试安插
    for (int i = 0; i < n; i++) {
        int deadline = games[i].t;
        int reward = games[i].r;

        // 截止时间如果超过n，其实等价于截止时间是n
        // 因为我们一共只有n个时间段
        if (deadline > n) deadline = n;

        // 核心逻辑：从截止时间往回找空位
        // 就像找座位一样，尽量坐后面，把前面留给别人
        for (int time = deadline; time >= 1; time--) {
            if (!used[time]) {
                // 找到空位了！
                used[time] = true;      // 占领
                totalReward += reward;  // 加分
                break;                  // 这个游戏安排好了，跳出内层循环，处理下一个游戏
            }
        }
    }

    cout << totalReward << endl;
}

int main() {
    // IO优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

6. 进阶思考（适合想拿满分的同学）

目前的解法是 $O(N^2)$。

• 外层循环 $N$ 次（遍历游戏）。
• 内层循环最坏 $N$ 次（查找空位）。
• 对于 $N=500$，$500^2 = 250,000$，非常快。

如果 $N$ 变大到 $10^5$ 怎么办？ 这时候 $O(N^2)$ 会超时。我们需要更高级的贪心策略：带悔棋的贪心（使用优先队列/小根堆）。

• 思路：按截止时间从小到大排序。
• 遍历每个游戏：
  • 先不管三七二十一，把它的奖励扔进一个“小根堆”（Min-Heap）。
  • 如果堆里元素的个数超过了当前的截止时间（说明做不完这么多游戏了），就把堆里最小的那个奖励扔掉（这就叫“反悔”，把位置腾给更值得的游戏）。
• 这样时间复杂度是 $O(N \log N)$。对于 GESP 五级，掌握上面的 $O(N^2)$ 方法通常已经足够通关。

---

上面的代码WA了，为什么？

你好！作为你的OI教练，我非常感谢你指出了这个问题。这是竞赛中非常典型且致命的错误——读题/输入格式解析错误。

即使你的贪心算法逻辑（核心思想）是完全完美的，如果输入数据的对应关系搞反了，拿到的分数就是 0 分。

1. 错误原因深度剖析

让我们对比一下我之前的代码和你提供的 AC 代码，就能立刻发现问题所在：

你提供的 AC 代码逻辑：

struct game{ int q, w; } a[511];
// q 被用作 j 的初始值 (j=a[i].q)，说明 q 代表【截止时间 Time】
// w 被累加进 ans (ans+=a[i].w)，且用于排序，说明 w 代表【奖金/价值 Reward】

// 输入部分：
for(int i=1;i<=n;i++) cin >> a[i].q; // 先读入的是 q (时间)
for(int i=1;i<=n;i++) cin >> a[i].w; // 后读入的是 w (奖金)

我之前的代码逻辑（错误点）：

// 我之前的错误假设：
// 先读入 games[i].r (奖金)
// 后读入 games[i].t (时间)

结论： 输入顺序反了！ 题目 B3872 的真实输入格式是：

• 第一行：$n$
• 第二行：$n$ 个整数，代表每个游戏的截止时间 $T_i$
• 第三行：$n$ 个整数，代表每个游戏的奖金 $R_i$

我的旧代码把第二行当成了奖金，第三行当成了时间，导致程序把“时间”作为排序依据去贪心，完全南辕北辙。

---

2. 修正后的标准题解代码 (NOIP C++14)

根据正确的输入顺序，我重新整理了标准代码。为了方便理解，我把变量名统一为 t (time) 和 r (reward)。

/**
 * 题目：B3872 [GESP202309 五级] 巧夺大奖
 * 修正点：严格遵循输入格式 -> 先读时间 T，后读奖金 R
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Game {
    int id;
    int t; // 截止时间 (Deadline)
    int r; // 奖金 (Reward)
};

// 贪心策略：优先做奖金高的
bool cmp(const Game &a, const Game &b) {
    return a.r > b.r; // 降序排列
}

bool used[505]; // 记录时间段是否被占用

void solve() {
    int n;
    cin >> n;

    vector<Game> games(n);

    // 【关键修正】
    // 题目输入格式：先输入一行时间限制
    for (int i = 0; i < n; i++) {
        cin >> games[i].t;
    }
    
    // 再输入一行奖金
    for (int i = 0; i < n; i++) {
        cin >> games[i].r;
        games[i].id = i;
    }

    // 1. 排序：按奖金从大到小
    sort(games.begin(), games.end(), cmp);

    // 初始化时间轴
    for (int i = 0; i <= n; i++) used[i] = false;

    long long totalReward = 0;

    // 2. 贪心决策
    for (int i = 0; i < n; i++) {
        // 截止时间不能超过 n (因为只有 n 个时间段)
        // 这一步优化很有必要，防止数组越界，同时也符合逻辑
        int deadline = min(games[i].t, n);
        
        // 从截止时间向前寻找空位
        // 核心思想：好位置留给期限更紧的人，自己尽量往后排
        for (int time = deadline; time >= 1; time--) {
            if (!used[time]) {
                used[time] = true;      // 占坑
                totalReward += games[i].r; // 拿钱
                break; // 安排好了，处理下一个游戏
            }
        }
    }

    cout << totalReward << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

---

3. 修正后的数据生成器 (1.in - 10.in)

由于输入格式变了，数据生成器也必须修改，否则生成的测试数据会导致你的 AC 代码运行出错。

修正逻辑：先生成并写入 T (时间) 行，再生成并写入 R (奖金) 行。

/**
 * B3872 数据生成器 - 修正版
 * 生成格式：
 * Line 1: N
 * Line 2: T1 T2 ... Tn (时间)
 * Line 3: R1 R2 ... Rn (奖金)
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

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

// 模拟 AC 代码的逻辑来生成 .out
bool cmp(const Game &a, const Game &b) { return a.r > b.r; }

long long solve(int n, vector<Game>& games) {
    sort(games.begin(), games.end(), cmp);
    vector<bool> used(n + 1, false);
    long long ans = 0;
    for (auto& g : games) {
        int deadline = min(g.t, n);
        for (int t = deadline; t >= 1; t--) {
            if (!used[t]) {
                used[t] = true;
                ans += g.r;
                break;
            }
        }
    }
    return ans;
}

void makeData(int fileId) {
    string inName = to_string(fileId) + ".in";
    string outName = to_string(fileId) + ".out";
    ofstream fin(inName);
    ofstream fout(outName);

    int N;
    // 数据规模分层
    if (fileId <= 3) N = 10;
    else if (fileId <= 7) N = 100;
    else N = 500;

    fin << N << endl;
    vector<Game> games(N);
    
    // 【修正点】先生成并输出时间 T
    for (int i = 0; i < N; i++) {
        // 特殊测试点构造
        if (fileId == 5) games[i].t = 1; // 极限情况：全在第1天截止
        else if (fileId == 6) games[i].t = N; // 极限情况：时间都很充裕
        else games[i].t = rand() % N + 1; // 正常随机
        
        fin << games[i].t << (i == N - 1 ? "" : " ");
    }
    fin << endl;

    // 【修正点】再生成并输出奖金 R
    for (int i = 0; i < N; i++) {
        games[i].r = rand() % 1000 + 1;
        fin << games[i].r << (i == N - 1 ? "" : " ");
    }
    fin << endl;

    // 计算标准答案并写入 .out
    fout << solve(N, games) << endl;
    
    fin.close();
    fout.close();
    cout << "Generated Case " << fileId << " (N=" << N << ") : Fixed Format T->R" << endl;
}

int main() {
    srand(time(0));
    for(int i=1; i<=10; i++) makeData(i);
    cout << "All data generated correctly." << endl;
    return 0;
}

教练总结

这次的“翻车”经历非常有教育意义：

1. 读题顺序：在 OI 比赛中，输入格式（Input Format）部分必须逐字阅读。特别是当有多个数组输入时，确认是“先 A 后 B”还是“先 B 后 A”。
2. 变量命名：你的 AC 代码中使用了 q 和 w。虽然代码能跑过，但在复杂题目中，建议使用更具语义的变量名，如 deadline/time 和 prize/reward，这样即使过了一个月再看代码，也能一眼看出哪个是钱，哪个是时间，不容易搞混。

现在你可以使用这个修正后的生成器来构建 OJ 数据了！加油！