LeetCode LCP 12. 小张刷题计划
题目描述
题意分析
按原顺序在
m天内完成所有题目，一道题不能拆到不同天，每天最多可以求助一次，免去某一道题的耗时。要求最小化所有天中的最大实际耗时，允许提前完成后不再做题。一天完成的题目必然是一个连续段。对确定的一段，求助最耗时的题一定最优，因此它的实际代价是
sum - max，其中sum为这段总耗时，max为其中最大耗时。
解法：二分答案 + 贪心分段
核心思路
[!blue]
先把求最优值转成判定：给定单日上限
limit，能否将全部题目分成不超过m个代价都不超过上限的连续段？上限越大，原本可行的分段仍然可行，所以可行性具有单调性，可以二分最小可行上限。判定时用
days记录已经开始的天数，sum、maxVal记录当天连续段的总和与最大值。加入一道耗时为t的题后，先更新这两个量，再计算sum - maxVal。新题可能成为当天最大值并被免去，不能只把它加到旧的实际耗时上。向一个段加入非负耗时的题，其代价不会下降：若新题没有成为最大值，代价增加
t；若它成为最大值，原来的最大值重新计入代价。因此一旦加入当前题超限，再加入后面的题也无法挽救这一天，可以把前面的最长合法前缀作为当天内容，从当前题开始新的一天。这样贪心分段得到的天数最少。任意其他合法方案的第一天都不能超过贪心选出的最长前缀；把它延长到贪心终点，第一天仍合法，后续各段只需删掉被提前完成的题。删除元素不会增加一段的
sum - max，整段被删空时还可以省去一天，所以总天数不会增加。对剩余题目重复这个调整，就得到贪心方案。换天时要令
sum = t、maxVal = t，让触发超限的当前题成为新一天的第一题。单题可以直接求助，代价为零，所以新段一定合法；如果天数已经超过m，贪心的最少天数也超限，立即判定失败。二分初始范围为零到总耗时。零可能是答案，总耗时则一定足够。当前
mid可行时，继续向左寻找更小上限；不可行时，只能增大上限。闭区间搜索结束后，left正是第一个可行值。
解题步骤
- 建立零到总耗时的二分范围。
- 给定上限，逐题维护当天总和与最大值。
- 超限则增加天数，并以当前题重新初始化当天状态。
- 根据天数是否超过 m 收缩范围，返回最小可行上限。
当
m不小于题目数量时，每天只做一题并求助，答案为零，现有判定会自然得到这个结果。等于limit的一天仍然合法，只在严格超限时换天。题目总耗时最多为 $10^9$，总和与二分边界均可使用int。
代码实现
class Solution {
public int minTime(int[] time, int m) {
int left = 0;
int right = 0;
for (int t : time) {
right += t;
}
// 闭区间二分最小的可行上限。
while (left <= right) {
int mid = left + (right - left) / 2;
if (canFinish(time, m, mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
// 上限为 limit 时，贪心地每天尽量多做，看天数是否不超过 m。
private boolean canFinish(int[] time, int m, int limit) {
int days = 1;
int sum = 0;
int maxVal = 0;
for (int t : time) {
sum += t;
maxVal = Math.max(maxVal, t);
// 当天代价 = 总和 - 最大值（求助掉最耗时的那道）。
if (sum - maxVal > limit) {
days++;
if (days > m) {
return false;
}
// 这道题推到新的一天，成为新段的首个元素。
sum = t;
maxVal = t;
}
}
return true;
}
}
func minTime(time []int, m int) int {
left, right := 0, 0
for _, t := range time {
right += t
}
// 闭区间二分最小的可行上限。
for left <= right {
mid := left + (right-left)/2
if canFinish(time, m, mid) {
right = mid - 1
} else {
left = mid + 1
}
}
return left
}
// 上限为 limit 时，贪心地每天尽量多做，看天数是否不超过 m。
func canFinish(time []int, m int, limit int) bool {
days := 1
sum := 0
maxVal := 0
for _, t := range time {
sum += t
if t > maxVal {
maxVal = t
}
// 当天代价 = 总和 - 最大值（求助掉最耗时的那道）。
if sum-maxVal > limit {
days++
if days > m {
return false
}
// 这道题推到新的一天，成为新段的首个元素。
sum = t
maxVal = t
}
}
return true
}
复杂度分析
- 时间复杂度：$O(n\log(S+2))$，S 为总耗时，每次判定线性扫描，包含初始统计与零上界情况。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 每天的代价是总和减最大值。
- 判断上限时尽量延长当前连续段，得到最少天数。
- 当前题导致超限后，应放入下一天而不是丢弃。
易错点总结
[!yellow]
- 不更新最大值就判断新段代价：新题可能成为应免去的最大项。
- 换天时把总和与最大值都清零：当前题被遗漏。
- 等于上限也强制换天：拒绝合法分段。
- 下界从一开始：每天一题时答案可能为零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 410. 分割数组的最大值 | 困难 | 同样最小化连续分段的最大代价，本题每段可免去最大一项，判定费用变为sum-max。 |