Skip to content

题解里面如果包含有目录，点击目录跳转后，题解的头几行会看不到 #1187

Open
Open
题解里面如果包含有目录，点击目录跳转后，题解的头几行会看不到#1187

Description

@mjiew
mjiew
opened on Jun 30, 2026

点击目录后， 目录的头几行看不见了：

Image

可以用于测试的题解：

兼职

点击展开目录

1. 题目信息

  • 题目来源：Q1068
  • 题目难度：提高−
  • 关键词/算法标签：贪心、并查集（DSU）、排序、任务调度
  • 时空限制：未明确给出（常规 1s / 256MB）

2. 题意理解

前置知识

阅读本题题解前，请确认你已掌握以下知识：

  • 贪心算法的基本思想
  • 并查集（DSU）的路径压缩
  • 排序算法
  • 基本的可行性分析（Hall 定理的简单形式）

输入描述

给定 $N$ 份工作和时间上限 $M$ 天。每份工作 $i$ 有两个参数：

  • $A_i$：延迟天数。如果在第 $d$ 天完成工作 $i$，则在第 $d + A_i$ 天获得报酬。
  • $B_i$：报酬值。

输出描述

在从今天（第 $0$ 天）起不超过 $M$ 天的时间内，能够获得的最大总报酬。

核心问题

每份工作有一个"最晚完成日"（deadline），每天最多做一份工作，求在 deadline 约束下选择若干工作使总报酬最大。这是一个经典的带截止时间的任务调度问题。

数据范围分析

  • $1 \leqslant N \leqslant 10^5$
  • $1 \leqslant M \leqslant 10^6$
  • $1 \leqslant A_i \leqslant 10^5$
  • $1 \leqslant B_i \leqslant 10^4$

注意：$A_i$ 与 $M$ 的大小关系会影响有效工作数量。当 $A_i > M$ 时，即使第 $0$ 天完成工作 $i$，报酬也在第 $A_i > M$ 天到达，超出时间上限。因此这类工作不可能被完成，应直接忽略。

分层解法概览

数据范围 解法 时间复杂度 空间复杂度
$N \leqslant 20$ 暴力枚举 $O(2^N \cdot N)$ $O(N)$
$N \leqslant 5000$ 动态规划 $O(N \cdot \min(N, M))$ $O(N)$
$N \leqslant 10^5,\ M \leqslant 10^6$ 贪心 + 并查集 $O(N \log N + M)$ $O(N + M)$

3. 题目分析

3.1 初步观察

首先，我们将题目描述转化为更清晰的数学形式。

关键转化：如果在第 $d$ 天完成工作 $i$，报酬在第 $d + A_i$ 天到达。要求 $d + A_i \leqslant M$，即 $d \leqslant M - A_i$。

令 $D_i = M - A_i$，称为工作 $i$ 的截止时间（deadline）。问题转化为：

有 $N$ 个工作，每个工作有截止时间 $D_i$ 和报酬 $B_i$。每天最多做一个工作。选择若干工作并安排在不同的天数上，使得每个工作都在其截止时间当天或之前完成，求最大总报酬。

原始问题:
  工作 i: 第 d 天完成 → 第 d + A_i 天获得报酬 B_i
  约束: d + A_i ≤ M

转化:
  令 D_i = M - A_i（工作 i 的最晚完成日）
  约束变为: d ≤ D_i

等价问题:
  N 个工作, 每个工作有截止时间 D_i 和报酬 B_i
  每天最多做一个工作
  求最大总报酬

题眼识别：这是一个经典的带截止时间的任务调度（Job Scheduling with Deadlines）问题。

3.2 暴力解法分析

最朴素的思路：枚举所有工作的子集，检查每个子集是否可行（能否安排在不冲突的天数上），取可行子集中的最大报酬。

可行性判定需要一个关键引理：

可行性引理：$k$ 个工作，截止时间分别为 $D_1 \leqslant D_2 \leqslant \cdots \leqslant D_k$（已排序），它们可以被 feasibly 安排（每个工作在一个不同的天数 $\leqslant$ 其截止时间）当且仅当对所有 $i = 1, 2, \ldots, k$，都有 $D_i \geqslant i - 1$。

证明：

必要性：假设这 $k$ 个工作被 feasibly 安排在了 $k$ 个不同的天 $d_1, d_2, \ldots, d_k$。考虑截止时间最小的前 $i$ 个工作，它们被安排在了 $i$ 个不同的天，且每天 $\leqslant$ 各自截止时间 $\leqslant D_i$。因此 $[0, D_i]$ 范围内至少有 $i$ 个不同的整数，即 $D_i + 1 \geqslant i$，也就是 $D_i \geqslant i - 1$。

充分性：如果 $D_i \geqslant i - 1$ 对所有 $i$ 成立，直接将第 $i$ 个工作安排在第 $i - 1$ 天。因为 $D_i \geqslant i - 1$，所以第 $i - 1$ 天 $\leqslant D_i$，合法。天数 $0, 1, \ldots, k-1$ 互不相同。因此这是一个可行安排。

$\blacksquare$

暴力解法的瓶颈：枚举 $2^N$ 个子集，每个子集需要 $O(N \log N)$ 排序 + $O(N)$ 检验，总复杂度 $O(2^N \cdot N \log N)$。当 $N > 20$ 时，$2^{20} \approx 10^6$，还能接受；但 $N = 30$ 时 $2^{30} \approx 10^9$，严重超时。

3.3 第一层 暴力枚举

💡 思考线索：为什么想到这一层解法？

  • 信号：$N \leqslant 20$，数据范围极小
  • 联想：$2^{20} \approx 10^6$，可以枚举所有子集
  • 模式匹配：小数据范围 → 暴力枚举所有方案

适用数据范围：$N \leqslant 20$

算法步骤：

  1. 计算每个工作的截止时间 $D_i = M - A_i$
  2. 枚举 $0$ 到 $2^N - 1$ 的每个 bitmask
  3. 对每个 bitmask，提取选中的工作，按截止时间排序
  4. 用可行性引理检验是否可行
  5. 可行则计算总报酬，更新最大值
点击展开：第一层解法 C++ 代码（n ≤ 20） 
#include <bits/stdc++.h>
using namespace std;

struct Job {
    int D, B; // D = 截止时间, B = 报酬
};

Job jobs[25];
int N, M;

// 检查选中的工作是否可行（能否安排在不冲突的天数内）
// 为什么这样检查？根据可行性引理：排序后第 i 个工作的截止时间必须 >= i
bool check(int mask) {
    int cnt = 0;
    int dl[25];
    for (int i = 0; i < N; i++) {
        if (mask & (1 << i)) {
            dl[cnt++] = jobs[i].D;
        }
    }
    // 按截止时间从小到大排序
    for (int i = 0; i < cnt - 1; i++)
        for (int j = i + 1; j < cnt; j++)
            if (dl[i] > dl[j]) {
                int tmp = dl[i]; dl[i] = dl[j]; dl[j] = tmp;
            }
    // 可行性引理：排序后第 i 个工作的截止时间必须 >= i
    for (int i = 0; i < cnt; i++) {
        if (dl[i] < i) return false;
    }
    return true;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        jobs[i].D = M - a; // 截止时间 = M - A_i
        jobs[i].B = b;
    }

    int best = 0;
    // 枚举所有子集
    for (int mask = 0; mask < (1 << N); mask++) {
        if (check(mask)) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                if (mask & (1 << i)) {
                    sum += jobs[i].B;
                }
            }
            if (sum > best) best = sum;
        }
    }

    printf("%d\n", best);
    return 0;
}

复杂度分析：

  • 时间：$O(2^N \cdot N^2)$（枚举 $2^N$ 个子集，每个子集排序 $O(N^2)$ 或 $O(N \log N)$）
  • 空间：$O(N)$

此解法仅适用于 $N \leqslant 20$。当 $N &gt; 20$ 时，$2^N$ 爆炸式增长，会超时。

3.4 第二层 动态规划

💡 思考线索：为什么想到这一层解法？

  • 信号：$N \leqslant 5000$，$O(N^2)$ 可过
  • 联想：排序后逐个考虑每个工作"选"或"不选" → 类似 0/1 背包
  • 模式匹配：从 $N$ 个物品中选若干使总价值最大 → 背包 DP

上一层的瓶颈：暴力枚举需要遍历 $2^N$ 个子集，指数级复杂度无法接受。我们需要一个多项式时间的算法。

思路分析：

将所有工作按截止时间 $D_i$ 从小到大排序。排序后，我们逐个考虑每个工作"选"或"不选"。

状态定义：$dp[j]$ = 从前 $i$ 个工作中恰好选 $j$ 个的最大总报酬。

为什么这样定义？ 因为排序后，如果我们选了 $j$ 个工作，且第 $i$ 个工作是其中之一（截止时间最大），那么可行性条件简化为 $j \leqslant D_i + 1$（由可行性引理，前 $j-1$ 个工作已 feasibly 安排，第 $j$ 个工作需要 $D_i \geqslant j - 1$）。

转移方程：对于第 $i$ 个工作（截止时间 $D_i$，报酬 $B_i$）：

$$dp[j] = \max(dp[j],\ dp[j-1] + B_i) \quad \text{其中 } j \leqslant D_i + 1$$

  • 不选工作 $i$：$dp[j]$ 不变
  • 选工作 $i$：$dp[j] = dp[j-1] + B_i$，要求 $j \leqslant D_i + 1$

为什么 $j \leqslant D_i + 1$ 就够了？ 因为前 $j-1$ 个选中的工作已经 feasibly 安排在 $j-1$ 天（由 $dp[j-1]$ 的合法性保证），它们可以重排到第 $0, 1, \ldots, j-2$ 天。工作 $i$ 的截止时间 $D_i \geqslant j - 1$，所以可以安排在第 $j - 1$ 天。

初始化：$dp[0] = 0$，$dp[j] = -1$（$j \geqslant 1$，表示不可达）。

答案：$\max_{j} dp[j]$。

点击展开：第二层解法 C++ 代码（n ≤ 5000） 
#include <bits/stdc++.h>
using namespace std;

struct Job {
    int D, B; // D = 截止时间, B = 报酬
};

const int MAXN = 5005;
Job jobs[MAXN];
int N, M;
long long dp[MAXN]; // dp[j] = 恰好选 j 个工作的最大报酬

bool cmp(const Job& a, const Job& b) {
    if (a.D != b.D) return a.D < b.D; // 按截止时间升序
    return a.B > b.B;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        jobs[i].D = M - a;
        jobs[i].B = b;
    }

    sort(jobs, jobs + N, cmp);

    // dp[j] = -1 表示不可达
    for (int j = 1; j <= N; j++) dp[j] = -1;
    dp[0] = 0;

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        if (jobs[i].D < 0) continue; // 截止时间 < 0 的工作不可能完成
        // 最多能选 min(i+1, D_i+1) 个工作
        int maxJ = i + 1;
        if (maxJ > jobs[i].D + 1) maxJ = jobs[i].D + 1;
        // 从大到小枚举 j，避免同一工作被重复选择（0/1 背包技巧）
        for (int j = maxJ; j >= 1; j--) {
            if (dp[j - 1] >= 0) {
                long long val = dp[j - 1] + jobs[i].B;
                if (val > dp[j]) dp[j] = val;
            }
        }
    }

    for (int j = 0; j <= N; j++) {
        if (dp[j] > ans) ans = dp[j];
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度分析：

  • 时间：排序 $O(N \log N)$ + DP $O(N \cdot \min(N, M))$。当 $N = 5000$ 时，$O(N^2) = 2.5 \times 10^7$，可以接受。
  • 空间：$O(N)$（一维 DP 数组）

此解法仅适用于 $N \leqslant 5000$。当 $N = 10^5$ 时，$O(N^2) = 10^{10}$，会超时。

3.5 第三层 贪心与并查集

💡 思考线索：为什么想到这一层解法？

  • 信号：$N \leqslant 10^5$，需要 $O(N \log N)$ 级别
  • 联想：带截止时间的任务调度 → 经典贪心模型
  • 模式匹配：每天一个"槽位"，需要快速找"最晚可用槽位" → 并查集

上一层的瓶颈：DP 的 $O(N \cdot \min(N, M))$ 在 $N = 10^5$ 时达到 $10^{10}$，无法接受。我们需要找到更高效的算法。

思路分析：

观察发现，这个问题具有拟阵（matroid）结构：可行工作集合满足子集封闭性和交换性。对于拟阵上的最优化问题，贪心算法是最优的。

贪心策略：

  1. 将所有工作按报酬 $B_i$ 从大到小排序
  2. 依次考虑每个工作，尝试将其安排在 $\leqslant D_i$ 的最晚可用天
  3. 如果能找到可用天，就安排该工作；否则跳过

为什么贪心是正确的？

下面给出交换论证的证明：

设贪心解为 $G$，最优解为 $O$，且 $\sum_{i \in O} B_i &gt; \sum_{i \in G} B_i$。

将 $G$ 和 $O$ 中的工作分别按报酬从大到小排序：$g_1, g_2, \ldots, g_k$ 和 $o_1, o_2, \ldots, o_m$。

由于贪心按报酬从大到小处理，$g_1$ 是所有工作中报酬最大的。如果 $g_1 \notin O$，我们可以将 $O$ 中报酬最小的工作替换为 $g_1$（因为 $g_1$ 报酬最大，替换后总报酬不降）。重复此过程，总可以将 $O$ 转化为 $G$ 而不降低总报酬，矛盾。

因此 $\sum_{i \in G} B_i \geqslant \sum_{i \in O} B_i$，贪心是最优的。$\blacksquare$

关键问题：如何高效找"最晚可用天"？

我们需要一个数据结构，支持以下操作：

  1. 查询 $\leqslant D$ 的最大可用天
  2. 将某天标记为"已占用"

候选数据结构分析：

数据结构 查询最晚可用天 标记占用 是否满足？
数组暴力扫描 $O(M)$ $O(1)$ 不满足：查询太慢，总复杂度 $O(NM)$
std::set $O(\log M)$（upper_bound） $O(\log M)$ 满足，但常数较大
线段树 $O(\log M)$ $O(\log M)$ 满足，但代码复杂
并查集（DSU） 均摊 $O(\alpha(M))$ 均摊 $O(\alpha(M))$ 满足，代码最短、常数最小

选择并查集的原因：代码最短、常数最小，且完全满足需求。

并查集的设计：

  • parent[x] 表示天 $x$ 的"代表元"
  • 初始时 parent[x] = x，表示每天都是可用的
  • 当某天 $d$ 被占用后，令 parent[d] = find(d - 1)，表示"找天 $d$ 时，请去找 $d - 1$ 以内的最晚可用天"
  • find(x) 返回 $\leqslant x$ 的最晚可用天；如果返回 $-1$，表示没有可用天
并查集工作原理图示：

初始状态 (M=4):
parent: [0]=0  [1]=1  [2]=2  [3]=3  [4]=4
          ↑      ↑      ↑      ↑      ↑
        可用    可用    可用    可用    可用

占用第 2 天后:
parent: [0]=0  [1]=1  [2]=1  [3]=3  [4]=4
          ↑      ↑      ↑      ↑      ↑
        可用    可用   指向1   可用    可用
               (第2天被占, find(2)→find(1)=1)

再占用第 1 天后:
parent: [0]=0  [1]=0  [2]=0  [3]=3  [4]=4
          ↑      ↑      ↑      ↑      ↑
        可用   指向0  指向0   可用    可用
              (第1天被占, find(1)→find(0)=0, find(2)路径压缩→0)

再占用第 0 天后:
parent: [0]=-1 [1]=-1 [2]=-1 [3]=3  [4]=4
          ↑      ↑      ↑      ↑      ↑
        不可用  不可用  不可用   可用    可用

代码实现：

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

struct Job {
    int D, B; // D = 截止时间（最晚完成日）, B = 报酬
};

const int MAXN = 100005;
const int MAXM = 1000005;
Job jobs[MAXN];
int parent[MAXM]; // 并查集：parent[x] 指向 x 以内最晚可用天
int N, M;

// 为什么用自定义 cmp 而不是 lambda？规范禁止 lambda
bool cmp(const Job& a, const Job& b) {
    return a.B > b.B; // 按报酬从大到小排序
}

// 并查集查找：找 x 以内最晚的可用天
// 为什么用并查集？因为需要高效查找"最晚可用天"，路径压缩使均摊复杂度为 O(α(M))
int find(int x) {
    if (x < 0) return -1; // 没有可用天
    if (parent[x] == x) return x; // x 本身可用
    return parent[x] = find(parent[x]); // 路径压缩：直接指向最终可用天
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        jobs[i].D = M - a; // 截止时间 = M - A_i
        jobs[i].B = b;
    }

    sort(jobs, jobs + N, cmp);

    // 初始化并查集：parent[i] = i 表示第 i 天可用
    for (int i = 0; i <= M; i++) parent[i] = i;

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        if (jobs[i].D < 0) continue; // 截止时间 < 0，无法在 M 天内获得报酬
        int day = find(jobs[i].D); // 找 deadline 以内最晚的空闲天
        if (day >= 0) {
            ans += jobs[i].B;
            // 占用 day 天后，将 day 指向 day-1 以内的最晚可用天
            // 为什么这样写？因为 find(day-1) 会返回 day-1 以内最晚可用天
            parent[day] = find(day - 1);
        }
    }

    printf("%lld\n", ans);
    return 0;
}

正解算法流程（摘要）：
步骤 1: 读入数据，计算每个工作的截止时间 D_i = M - A_i
步骤 2: 按报酬 B_i 从大到小排序
步骤 3: 初始化并查集 parent[i] = i（0 ≤ i ≤ M）
步骤 4: 依次处理每个工作，找 ≤ D_i 的最晚可用天
步骤 5: 若找到可用天，累加报酬并占用该天
步骤 6: 输出总报酬

3.6 样例逐步演示

以样例 1 为例，逐步展示算法执行过程。

样例输入：

3 4
4 3
4 1
2 2

步骤 1：计算截止时间

工作 $A_i$ $B_i$ $D_i = M - A_i$
1 4 3 0
2 4 1 0
3 2 2 2

步骤 2：按报酬从大到小排序

顺序 工作 $D_i$ $B_i$
1 1 0 3
2 3 2 2
3 2 0 1

步骤 3：初始化并查集

parent: [0]=0  [1]=1  [2]=2  [3]=3  [4]=4

步骤 4：处理工作 1（D=0, B=3）

  • find(0) → parent[0] = 0 → 返回 0
  • 第 $0$ 天可用，安排工作 1
  • ans += 3 = 3
  • parent[0] = find(-1) = -1
parent: [0]=-1 [1]=1  [2]=2  [3]=3  [4]=4
         ↑ 不可用

步骤 5：处理工作 3（D=2, B=2）

  • find(2) → parent[2] = 2 → 返回 2
  • 第 $2$ 天可用，安排工作 3
  • ans += 2 = 5
  • parent[2] = find(1) = 1
parent: [0]=-1 [1]=1  [2]=1  [3]=3  [4]=4
         ↑      ↑      ↑
       不可用  可用   指向1

步骤 6：处理工作 2（D=0, B=1）

  • find(0) → parent[0] = -1 → 返回 -1
  • 没有可用天，跳过

最终输出：ans = 5 ✓

4. 复杂度分析总结

时间复杂度

算法部分 来源 单次复杂度 执行次数 该项总复杂度
排序 对 $N$ 个工作按 $B_i$ 降序排序 $O(\log N)$（比较） 排序共 $O(N \log N)$ $O(N \log N)$
DSU 初始化 初始化 parent[0..M] $O(1)$ $M + 1$ 次 $O(M)$
DSU 查找 每个工作调用一次 find(D_i) 均摊 $O(\alpha(M))$ 最多 $N$ 次 $O(N \cdot \alpha(M))$
DSU 合并 占用天时执行 parent[day] = find(day-1) 均摊 $O(\alpha(M))$ 最多 $N$ 次 $O(N \cdot \alpha(M))$

总时间复杂度：$O(N \log N) + O(M) + O(N \cdot \alpha(M)) = $ $O(N \log N + M)$

其中 $\alpha(M)$ 是反 Ackermann 函数，对于所有实际数据规模 $\alpha(M) \leqslant 4$，可视为常数。

空间复杂度

数组/数据结构 大小 类型 占用空间
jobs[] $10^5 + 5$ struct Job（8 字节） 约 800 KB
parent[] $10^6 + 5$ int（4 字节） 约 4 MB

总空间复杂度：$O(N + M)$，约 5 MB，远在 256 MB 限制内。

总结表格

复杂度类型 分析
时间复杂度 排序 $O(N \log N)$ + DSU 初始化 $O(M)$ + DSU 操作 $O(N \cdot \alpha(M))$，总复杂度 $O(N \log N + M)$
空间复杂度 jobs[] $O(N)$ + parent[] $O(M)$，总空间 $O(N + M)$
正确性 基于拟阵上的贪心算法最优性，并通过交换论证严格证明

5. 多种解法 贪心与优先队列

除了贪心 + 并查集，还存在另一种同样能 AC 的解法：贪心 + 优先队列（小根堆）。

解法名称

贪心 + 优先队列（小根堆）

核心思想

按截止时间从小到大处理工作，维护一个已选工作报酬的小根堆。对于每个工作：

  • 如果堆的大小 $\leqslant D_i$，说明还有空位，直接加入
  • 否则，如果当前工作报酬 $&gt;$ 堆顶（已选工作中报酬最小的），则替换

完整推导

排序方式：按截止时间 $D_i$ 从小到大排序。

维护什么：一个小根堆，存储已选工作的报酬值。堆的大小 $|S|$ 表示已选工作的数量。

处理逻辑：

对于第 $i$ 个工作（截止时间 $D_i$，报酬 $B_i$）：

  1. 如果 $|S| \leqslant D_i$：说明已选工作数量 $\leqslant D_i$，而 $D_i + 1$ 天（$0$ 到 $D_i$）中至少有 $D_i + 1 - |S| \geqslant 1$ 天是空的。所以可以直接加入工作 $i$。
  2. 如果 $|S| &gt; D_i$（即 $|S| = D_i + 1$，因为之前 $|S| \leqslant D_i + 1$）：所有 $D_i + 1$ 天都被占用了。如果 $B_i > $ 堆顶（已选工作中报酬最小的），则替换掉堆顶，总报酬增加。

正确性证明：

替换后，堆的大小不变（仍为 $D_i + 1$），且所有已选工作的截止时间都 $\leqslant D_i$。由可行性引理，$D_i + 1$ 个工作安排在 $D_i + 1$ 天（$0$ 到 $D_i$）上是可行的。

代码实现

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

struct Job {
    int D, B; // D = 截止时间, B = 报酬
};

const int MAXN = 100005;
Job jobs[MAXN];
int N, M;

bool cmp(const Job& a, const Job& b) {
    if (a.D != b.D) return a.D < b.D; // 按截止时间升序
    return a.B > b.B;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        jobs[i].D = M - a;
        jobs[i].B = b;
    }

    sort(jobs, jobs + N, cmp);

    // 小根堆：维护已选工作的报酬，堆顶是最小报酬
    // 为什么用小根堆？需要快速找到并替换已选工作中报酬最小的那个
    priority_queue<int, vector<int>, greater<int> > pq;

    for (int i = 0; i < N; i++) {
        if (jobs[i].D < 0) continue;
        if ((int)pq.size() <= jobs[i].D) {
            // 还有空位（已选数量 ≤ D_i），直接加入
            pq.push(jobs[i].B);
        } else if (!pq.empty() && pq.top() < jobs[i].B) {
            // 没有空位，但当前工作报酬更高，替换掉最小的
            pq.pop();
            pq.push(jobs[i].B);
        }
    }

    long long ans = 0;
    while (!pq.empty()) {
        ans += pq.top();
        pq.pop();
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度分析

  • 时间：排序 $O(N \log N)$ + 堆操作 $O(N \log N)$ = $O(N \log N)$
  • 空间：$O(N)$（堆最多存 $N$ 个元素）

6. 解法对比与演化

对比表格

对比维度 贪心 + 并查集 贪心 + 优先队列
核心算法 贪心 + DSU 贪心 + 小根堆
排序方式 按报酬降序 按截止时间升序
时间复杂度 $O(N \log N + M)$ $O(N \log N)$
空间复杂度 $O(N + M)$ $O(N)$
代码复杂度 中等 简单
常数因子 小 中
思维难度 高 中
可扩展性 强（可输出具体方案） 弱（只能输出最优值）

本质联系

两种解法都是拟阵上贪心算法的不同实现：

  • 并查集版：按报酬从大到小处理，显式地将每个工作分配到具体的天。DSU 用于高效查找"最晚可用天"。
  • 优先队列版：按截止时间从小到大处理，隐式地维护已选工作集合。堆用于快速替换报酬最小的工作。

两者殊途同归，最终选出的工作集合是相同的（在报酬不重复的情况下）。

解法演化

暴力枚举 (O(2^N · N))
    ↓ 发现：排序后可以用可行性引理 O(N) 检验
    ↓ 优化：用 DP 代替枚举
动态规划 (O(N · min(N, M)))
    ↓ 发现：可行集构成拟阵，贪心最优
    ↓ 优化：用贪心 + 高效数据结构
贪心 + 并查集 / 优先队列 (O(N log N + M) / O(N log N))

7. 常见错误与易错点分析

7.1 常见错误思路

错误思路一：按截止时间从早到晚贪心，选报酬最大的

  • 为什么看起来对：EDF（最早截止优先）是经典的可行调度算法，直觉上"先做紧急的"很合理
  • 反例：$N = 2, M = 1$，工作 $(A=1, B=1), (A=1, B=100)$，截止时间都是 $D=0$。EDF 可能选了 $B=1$ 而错过 $B=100$
  • 错误本质：EDF 保证可行性，但不保证最优性；没有考虑报酬权值

错误思路二：按报酬从大到小贪心，但安排到最早可用天

  • 为什么看起来对：报酬最大的工作优先安排，直觉正确
  • 反例：$N = 3, M = 2$。工作：$(D=1, B=100), (D=0, B=10), (D=0, B=10)$。如果将 $B=100$ 安排在第 $0$ 天（最早可用），则 $D=0$ 的两个工作无法安排（第 $0$ 天被占），总计 $100$。正确做法是将 $B=100$ 安排在第 $1$ 天（最晚可用天），留第 $0$ 天给 $D=0$ 的工作，总计 $110$
  • 错误本质：最早可用天会"挤占"后面截止时间更早的工作的空间；必须安排在最晚可用天，为后面的工作留出余地

错误思路三：认为答案可能超出 int 范围而盲目使用 long long，或不分析就使用 int

  • 分析：最大答案 $= \min(N, M) \times \max(B_i) = 10^5 \times 10^4 = 10^9$。$10^9 < 2^{31} - 1 \approx 2.1 \times 10^9$，所以 int 足够。但使用 long long 更安全且无性能损失
  • 建议：使用 long long，但要知道为什么不会溢出

7.2 代码易错点

  1. 截止时间计算错误

    • 错误：写成 D = A 或 D = M + A
    • 正确：D = M - A（因为 $d + A \leqslant M \Rightarrow d \leqslant M - A$）
    • 后果：WA

  2. 未处理 $D_i &lt; 0$ 的情况

    • 错误：直接对所有工作调用 find(D_i)，当 $D_i &lt; 0$ 时可能数组越界
    • 正确：if (jobs[i].D < 0) continue;
    • 后果：RE 或 WA

  3. 并查集未初始化到 $M$

    • 错误：只初始化到 $N$ 或 $\max(D_i)$
    • 正确：初始化 parent[0..M]，因为 $D_i$ 最大为 $M - 1$
    • 后果：RE 或 WA

  4. find 函数未处理 $x &lt; 0$

    • 错误：find(-1) 导致数组越界
    • 正确：if (x < 0) return -1;
    • 后果：RE

  5. 排序方向搞反

    • 错误：按报酬从小到大排序
    • 正确：按报酬从大到小排序
    • 后果：WA（贪心策略失效）

8. 边界与特殊情况处理

情况 分析 代码处理
所有 $A_i &gt; M$ 所有工作截止时间 $&lt; 0$，无法完成任何工作 D_i < 0 时 continue，答案为 $0$
$N = 1$ 只有一份工作，能做就做 算法自然处理：$D_0 \geqslant 0$ 则安排，否则跳过
$M$ 非常大 所有工作都能完成（$D_i \geqslant N$） 算法自然处理：所有工作都能找到可用天
多个工作截止时间相同 需要竞争有限的天数 并查集自动处理：每次找最晚可用天，冲突时自动跳过
答案为 $0$ 没有任何工作能在 $M$ 天内完成 样例 3 即为这种情况，算法输出 $0$

9. 解题总结

本题核心 trick

将"延迟 $A_i$"转化为"截止时间 $D_i = M - A_i$"，从而将原问题等价转化为经典的带截止时间任务调度问题。然后利用拟阵上贪心的最优性，按报酬从大到小排序，用并查集高效查找最晚可用天。

可复用的解题模式

  1. 延迟 → 截止时间的转化：适用于所有"完成时间 + 延迟 ≤ 上限"的问题
  2. 贪心 + 并查集找最晚可用槽位：适用于所有"每个任务有截止时间、每个槽位最多放一个任务"的调度问题
  3. 可行性引理：排序后 $D_i \geqslant i - 1$ 是判断任务集合可调度性的充要条件

一句话记忆点

看到"带截止时间的任务调度，每个槽位最多一个任务" → 按价值排序 + 并查集找最晚可用天。

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions