高效工作

GitHub跳转原题关系图返回列表

将资金收支约束等价转化为截止时间模型,按截止时间升序考虑,并利用带反悔的贪心求解最多工作数。

OJ: roj

题目 ID: 5018

难度:提高+/省选-

标签:贪心优先队列

创建: 2026-10-08 20:06

更新: 2026-10-08 20:06

形式化题目

有 NN 项任务,初始资本为 MM。对于第 ii 项任务:

  • 在开始该任务前,手里的资金必须 ≥Di\ge D_i(不能借钱)。
  • 完成任务后获得 CiC_i 的奖励,即完成后的资金变为原来的金额减去 DiD_i 再加上 CiC_i。
  • 给定保证 Ci<DiC_i < D_i,即每次完成任务净消耗资金 pi=Di−Ci>0p_i = D_i - C_i > 0。

题目求在任意选择执行顺序、且每项任务最多只能做一次的前提下,最多能做完多少项任务。

数据范围

  • 1≤N≤50001 \le N \le 5000
  • 0≤Ci<Di≤50000 \le C_i < D_i \le 5000
  • 1≤Di,M≤50001 \le D_i, M \le 5000

注:本题提供的测试数据是自行生成的非官方数据,且数据为了兼容性,其给定的序列顺序恰好已经被构造成了基于截止时间升序(EDD序)。实际上,题目并未规定执行顺序,你可以自由安排工作的执行顺序。

正解

思路

这是一道经典的带反悔的贪心题,核心在于如何把复杂的资金收支限制转化为经典的单机调度模型。

1. 模型转化

假设当前手中剩余的资金为 curcur,如果要能够进行任务 ii,必须满足: cur≥Dicur \ge D_i

对于一个任务,其净消耗为 pi=Di−Ci>0p_i = D_i - C_i > 0。 如果在开始第 ii 项任务之前,我们已经完成了一个集合 SS 中的任务,那么我们当前的资金为: cur=M−∑j∈Spjcur = M - \sum_{j \in S} p_j

将这个代入前面的条件: M−∑j∈Spj≥Di  ⟺  ∑j∈Spj≤M−DiM - \sum_{j \in S} p_j \ge D_i \iff \sum_{j \in S} p_j \le M - D_i

为了方便把任务 ii 本身也算进“已完成任务的消耗”中,我们在等式两边同时加上任务 ii 的消耗 pip_i: ∑j∈Spj+pi≤M−Di+pi=M−Ci\sum_{j \in S} p_j + p_i \le M - D_i + p_i = M - C_i

至此,原问题等价于: 将每一项任务看作一个处理时间为 pi=Di−Cip_i = D_i - C_i 的工作,那么 di=M−Cid_i = M - C_i 就是这项工作的截止时刻。我们必须在时刻 did_i 之前完成这项工作。这便被成功归约为了单机调度模型 1∣∣∑Uj1||\sum U_j(最小化误期工作数问题)。

2. Moore-Hodgson 反悔贪心

对于 1∣∣∑Uj1||\sum U_j 模型,经典的最优算法是 Moore-Hodgson 算法(反悔贪心):

  1. 我们将所有任务按照截止时间 di=M−Cid_i = M - C_i 升序排序(等价于按 CiC_i 降序排序)。
  2. 从左到右遍历任务,尝试将其加入完成列表,同时将该任务的净消耗 pip_i 放入大根堆。
  3. 如果加入该任务后,总耗时超出了它的截止时刻(即 used>diused > d_i),我们就从大根堆中取出净消耗 pp 最大的任务丢弃(反悔),并将 usedused 减去丢弃任务的耗时。
  4. 遍历结束后,大根堆中的元素个数就是我们最多能完成的任务数。

3. 常见误区:应该按什么反悔?

在反悔时,我们必须丢弃净消耗 pi=Di−Cip_i = D_i - C_i 最大的,而不是只看 CiC_i 最大的。 这是因为我们的目标是让接下来的可用时间(即资金)尽可能多。换出净消耗 pp 更大的任务,意味着我们释放了更多的资金去安排后续任务。CC 大并不等于回钱多(或者说净消耗小),净消耗的大小是由 p=D−Cp = D - C 决定的。

此外,由于我们已经按截止时间 did_i 升序扫描,被换出的项其截止时间一定不大于当前的截止时间。因此换出操作只会减少总耗时,给后续任务腾出空间,而被换出的任务即使回到序列中,由于它的截止时间偏前,也无法再被加入。这保证了贪心过程不重不漏,不需要回溯。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 20:00
# update_at: 2026-10-08 20:00

import sys
from heapq import heappush, heappop

# 每项工作编码成 (截止时刻 d_i = M - C_i, 净支出 p_i = D_i - C_i)
type Jobs = list[tuple[int, int]]


def max_jobs(jobs: Jobs) -> int:
    """反悔贪心解单机 1||ΣU_j:按截止时刻升序接工作,超时则退掉净支出最大的一项。"""
    used = 0                 # 已接工作的总净支出
    chosen: list[int] = []   # 已接工作的净支出取负入堆 => 小根堆当大根堆用
    for deadline, cost in jobs:
        used += cost
        heappush(chosen, -cost)
        if used > deadline:
            dropped = heappop(chosen)  # 堆里是负数,加回 used 等于退掉该项的净支出
            used += dropped
    return len(chosen)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    m = next(data)

    spend = [next(data) for _ in range(n)]   # 题面的 D_i
    reward = [next(data) for _ in range(n)]  # 题面的 C_i

    # 做第 i 项工作前需要手上钱 >= D_i,即此前总净支出 <= M - D_i,
    # 等价于"必须在时刻 d_i = M - C_i 前完成处理时间为 p_i 的工作"。
    # EDD(按 d_i 升序,即 C_i 降序)是"该集合能被完成"的充分顺序。
    jobs: Jobs = sorted((m - c, d - c) for d, c in zip(spend, reward))

    print(max_jobs(jobs))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 20:00
 * update_at: 2026-10-08 20:00
 */

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;

const int MAXN = 5005; // 题面 N 上限

struct Job {
    ll deadline; // 截止时刻 d_i = M - C_i:做完第 i 项工作时手上钱最少只能是 M - d_i
    ll cost;     // 净支出 p_i = D_i - C_i > 0:做完这项工作上钱恰好少这么多
};

Job job[MAXN];   // job[1..n],按 deadline 升序排好后的工作
ll money;        // 初始钱数 M

// 按截止时刻升序(即 C_i 降序)排;并列时按净支出升序,平局顺序不影响答案
bool cmp_job(const Job& a, const Job& b) {
    if (a.deadline != b.deadline) return a.deadline < b.deadline;
    return a.cost < b.cost;
}

// 反悔贪心(Moore-Hodgson 解单机 1||ΣU_j):先把工作接进来,一旦已接工作的总净支出
// 超过当前截止时刻,就退掉已接工作中净支出最大的那一项(计数不变、回钱最多)。
void solve() {
    ll n;
    if (!(cin >> n >> money)) return;

    for (ll i = 1; i <= n; i++) cin >> job[i].cost; // 先存 D_i,稍后减去 C_i 得净支出
    for (ll i = 1; i <= n; i++) {
        ll c;
        cin >> c;
        job[i].cost -= c;             // p_i = D_i - C_i
        job[i].deadline = money - c;  // d_i = M - C_i
    }

    sort(job + 1, job + n + 1, cmp_job);

    priority_queue<ll> chosen; // 已接工作的净支出,大根堆方便反悔丢最大者
    ll used = 0;               // 已接工作的总净支出
    for (ll i = 1; i <= n; i++) {
        used += job[i].cost;
        chosen.push(job[i].cost);
        if (used > job[i].deadline) { // 当前截止时刻已装不下,反悔丢掉最大的一项
            used -= chosen.top();
            chosen.pop();
        }
    }

    cout << chosen.size() << "\n";
}

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

复杂度

  • 时间复杂度:排序需要 O(Nlog⁡N)O(N \log N) 的时间;遍历每个任务并进行优先队列的 push 和可能的一次 pop 操作,最坏情况下单次 O(log⁡N)O(\log N),这部分也是 O(Nlog⁡N)O(N \log N)。总体时间复杂度为 O(Nlog⁡N)O(N \log N)。
  • 空间复杂度:存储所有的任务和优先队列需要 O(N)O(N) 的空间。

总结

  • 等式代换与模型归约:这是本题最核心的一步。将“先花 DiD_i 再得 CiC_i”且“不能借钱”的条件推导为 M−∑j∈Spj≥Di  ⟺  ∑j∈Spj≤M−CiM - \sum_{j\in S} p_j \ge D_i \iff \sum_{j\in S} p_j \le M - C_i,从而将问题完美映射到带有截止时间的单机调度模型。
  • Moore-Hodgson 反悔贪心的承重实验:通过反事实的实验能够清楚看到关键代码的作用:
    1. jobs[i].deadline = money - c[i] 这是被验证的严格条件,如果把它改错成 d[i] 或者 c[i],在真实数据上都会失败。
    2. 反悔时退出的必须是净支出 pip_i 最大的工作(使用大根堆),如果换成小根堆(即退掉耗时最小的工作),真实数据同样会报错。
  • 顺序无要求:题面只问“最多能做完几项工作”,不限制任何顺序。虽然提供的测试数据本身是按 EDD 序生成的,但那是出题时的构造约定。我们的程序先按 did_i 排序的做法,是对任意乱序输入的泛化解法。
  • 贪心中的丢弃操作是安全且单向的,因为按升序扫描时,丢出项不仅降低了当前的消耗,而且由于它更早到期,后续它也没有可能再混进来,保证了 O(Nlog⁡N)O(N \log N) 复杂度的准确性和高效性。