将资金收支约束等价转化为截止时间模型,按截止时间升序考虑,并利用带反悔的贪心求解最多工作数。
OJ: roj
题目 ID: 5018
难度:提高+/省选-
标签:贪心优先队列
创建: 2026-10-08 20:06
更新: 2026-10-08 20:06
形式化题目
有
- 在开始该任务前,手里的资金必须
(不能借钱)。 - 完成任务后获得
的奖励,即完成后的资金变为原来的金额减去 再加上 。 - 给定保证
,即每次完成任务净消耗资金 。
题目求在任意选择执行顺序、且每项任务最多只能做一次的前提下,最多能做完多少项任务。
数据范围
注:本题提供的测试数据是自行生成的非官方数据,且数据为了兼容性,其给定的序列顺序恰好已经被构造成了基于截止时间升序(EDD序)。实际上,题目并未规定执行顺序,你可以自由安排工作的执行顺序。
正解
思路
这是一道经典的带反悔的贪心题,核心在于如何把复杂的资金收支限制转化为经典的单机调度模型。
1. 模型转化
假设当前手中剩余的资金为
对于一个任务,其净消耗为
将这个代入前面的条件:
为了方便把任务
至此,原问题等价于:
将每一项任务看作一个处理时间为
2. Moore-Hodgson 反悔贪心
对于
- 我们将所有任务按照截止时间
升序排序(等价于按 降序排序)。 - 从左到右遍历任务,尝试将其加入完成列表,同时将该任务的净消耗
放入大根堆。 - 如果加入该任务后,总耗时超出了它的截止时刻(即
),我们就从大根堆中取出净消耗 最大的任务丢弃(反悔),并将 减去丢弃任务的耗时。 - 遍历结束后,大根堆中的元素个数就是我们最多能完成的任务数。
3. 常见误区:应该按什么反悔?
在反悔时,我们必须丢弃净消耗
此外,由于我们已经按截止时间
代码
#!/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()/**
* 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;
}复杂度
- 时间复杂度:排序需要
的时间;遍历每个任务并进行优先队列的 push和可能的一次pop操作,最坏情况下单次,这部分也是 。总体时间复杂度为 。 - 空间复杂度:存储所有的任务和优先队列需要
的空间。
总结
- 等式代换与模型归约:这是本题最核心的一步。将“先花
再得 ”且“不能借钱”的条件推导为 ,从而将问题完美映射到带有截止时间的单机调度模型。 - Moore-Hodgson 反悔贪心的承重实验:通过反事实的实验能够清楚看到关键代码的作用:
jobs[i].deadline = money - c[i]这是被验证的严格条件,如果把它改错成d[i]或者c[i],在真实数据上都会失败。- 反悔时退出的必须是净支出
最大的工作(使用大根堆),如果换成小根堆(即退掉耗时最小的工作),真实数据同样会报错。
- 顺序无要求:题面只问“最多能做完几项工作”,不限制任何顺序。虽然提供的测试数据本身是按 EDD 序生成的,但那是出题时的构造约定。我们的程序先按
排序的做法,是对任意乱序输入的泛化解法。 - 贪心中的丢弃操作是安全且单向的,因为按升序扫描时,丢出项不仅降低了当前的消耗,而且由于它更早到期,后续它也没有可能再混进来,保证了
复杂度的准确性和高效性。