ZYF056 完成所有任务的最少初始能量
大约 4 分钟
ZYF056 完成所有任务的最少初始能量
【算法】 贪心、排序
【C++】 结构体、sort、long long
【难度】 普及/提高−
一、题目简述
有 个任务,每个任务有两个参数 :
- :完成该任务消耗的能量
- :开始该任务前必须拥有的最低能量()
你可以按任意顺序完成任务。求完成所有任务的最少初始能量。
| 变量 | 范围 |
|---|---|
二、解题思路
2.1 问题分析
假设我们选定了一个任务顺序 。设初始能量为 ,则必须满足:
整理得:
所以最少初始能量就是:
问题转化为:如何排列任务顺序,使这个最大值最小?
2.2 贪心策略 —— 为什么按「最低能量 − 实际消耗」排序?
考虑两个相邻任务 和 ,假设在它们之前已经消耗了 的能量:
- 先 1 后 2:需要
- 先 2 后 1:需要
我们希望 (约去 )。
定义「额外能量需求」(即任务 要求的能量比它实际消耗多出的部分),代入 :
当 时,"先 1 后 2"往往更优。直觉上:
越大的任务,对初始能量的"额外要求"越高,应该尽量排在前面,趁能量还充足时先把它做完。
这引出了贪心规则:按 从大到小排序。当 相同时,顺序任意。
2.3 手动模拟
以样例 1 为例:
(1, 2), (2, 4), (4, 8)
d值: 1, 2, 4按 降序排列:
| 步骤 | 任务 | 开始前累计消耗 | 需要能量 | 累计消耗变为 |
|---|---|---|---|---|
| 1 | (4, 8) | 0 | 4 | |
| 2 | (2, 4) | 4 | 6 | |
| 3 | (1, 2) | 6 | 7 |
最大值 ,即最少初始能量为 。
2.4 算法步骤
- 读入所有任务,存入结构体数组
- 按 从大到小排序
- 遍历排序后的任务序列,维护前缀消耗
pref:ans = max(ans, m_i + pref)pref += a_i
- 输出
ans
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Task {
int actual, minimum, diff;
} t[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> t[i].actual >> t[i].minimum;
t[i].diff = t[i].minimum - t[i].actual;
}
// 按 d = minimum - actual 从大到小排序
sort(t, t + n, [](const Task &a, const Task &b) {
return a.diff > b.diff;
});
long long ans = 0; // 累计需要额外补的能量
long long cur = 0; // 当前剩余能量
for (int i = 0; i < n; i++) {
if (cur < t[i].minimum) {
// 能量不够开始这个任务,需要一开始就多准备一些
ans += t[i].minimum - cur;
cur = t[i].minimum;
}
cur -= t[i].actual; // 完成任务,消耗能量
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,排序占主导, 轻松通过。
- 空间复杂度:,存储所有任务的结构体数组。
五、知识扩展
5.1 另一种理解方式 —— 反向推导
从"完成所有任务后剩余能量为 "开始,逆序考虑每个任务:
- 做完最后一个任务后剩 ,做之前至少需要
- 依次向前推出每个任务开始前的最小能量
逆推公式与正向等价,最终得到相同的贪心结论。e
5.2 易错点
排序依据:按 降序,而不是按 降序或 升序。反例:
(3, 100), d=97 (100, 101), d=1若按 降序排 ⇒ 先做 (100, 101),需要 ;正解为先做 (3, 100),只需 。
溢出: 最大可达 ,
int刚好够(约 ),但建议用long long防止极端数据。相同时:顺序无关紧要,
sort的不稳定排序不影响答案正确性。
5.3 类似题目
- LeetCode 1665. Minimum Initial Energy to Finish Tasks —— 本题原题
- 洛谷 P2949 工作调度 —— 类似的贪心排序思路
