LeetCode LCP 12. 小张刷题计划

2025-01-31 HGNULB 约 12 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ LCP 12. 小张刷题计划

题意分析

time 数组按顺序给出每道题的耗时，小张要在 m 天内按原顺序刷完全部题目。每一天他可以向朋友求助至多一次，被求助的那道题当天不消耗他的时间。求「刷题时间最长的那一天」的耗时最小可能是多少。

三个约束要读准。第一，题目顺序不能打乱，所以每天做的是数组中一段连续的题；把 m 天的安排看成把数组切成不超过 m 个连续段。第二，每天最多求助一次，也就是每一段里可以免掉恰好一道题的耗时——显然应该免掉这一段里耗时最大的那道，因为免哪道都只求助一次，免最大的收益最大。于是一段 [l, r] 的实际代价是 sum(l..r) - max(l..r)。第三，要最小化的是所有天里的最大值，这是典型的「最小化最大值」。

「最小化最大值」加上「代价随限制单调」这两个特征，几乎是在明说二分答案。理由是：如果每天耗时上限定为 T 可行，那么上限放宽到 T + 1 必然也可行（同一套分段方案照搬即可）；反过来 T 不可行则所有更小的值都不可行。可行性关于 T 单调，因此答案是「可行区间的左端点」，可以二分。

约束里题目数不超过 $10^5$、每题耗时不超过 $10^4$，总和上界约 $10^9$，仍在 32 位整数内。二分的值域跨度是 $10^9$，需要约 30 次迭代，每次判定 $O(n)$，总量 $3 \times 10^6$，完全可行；而直接做区间 DP 是 $O(n^2 m)$，规模上不可能。

边界方面：m 大于等于题目数时，每天做一题并求助掉它，答案是 0；只有一天时，答案是总和减去最大值；数组只有一个元素时答案也是 0。这些都应该由主逻辑自然覆盖，而不是靠特判。

解法：二分答案 + 贪心分段

核心思路

先看直接 DP 的思路：f[i][j] 表示前 i 道题用 j 天完成时的最优「最大单日耗时」，转移要枚举最后一天从哪里开始。状态数是 $O(n m)$，转移再乘 $O(n)$，总量 $O(n^2 m)$，n 到 $10^5$ 时完全不可行。

瓶颈在于「同时决定分段位置和最优值」这件事太重。二分答案的思路是把最优化问题反过来变成判定问题：不去问「最小的最大值是多少」，而是问「给定上限 T，能不能在 m 天内完成」。判定问题好做得多，而由前面论证的单调性，对 T 做二分就能逼出答案。

判定函数 canFinish(T) 用贪心：从左往右扫，当前这一天能多做一题就多做一题，直到再加一题就会让当天代价超过 T，才开启新的一天。这个贪心正确是因为——在上限固定的前提下，每一天做得越多，剩给后面的题就越少，需要的天数只会更少或相等；把某天提前结束绝不会让总天数变小。所以贪心分段用到的天数就是该上限下的最少天数，与 m 比较即可判定。

判定里的代价计算是本题最精细的一处。一段的代价是 sum - max，所以扫描时要同时维护当前段的 sum 与 max。每加入一道题 t，先更新 sum += t 和 max = Math.max(max, t)，再检查 sum - max > T；若超了，说明这道题不能留在当前段，于是天数加一，并把当前段重置为只含这道题（sum = t、max = t）。

重置成 {t} 而不是清零，是因为这道题必须落到新的一天里去，它是新段的第一个元素。注意单独一道题的代价是 t - t = 0，永远不会超过任何非负的 T，所以重置后一定合法，不会出现「一道题都放不下」的死循环——这也顺带说明了本题不存在无解，答案下界就是 0。

二分的边界：左端取 0（最好情况，每天只做一题并求助掉），右端取所有耗时之和（最坏情况，一天做完且只免掉最大的一道，实际代价还更小，所以这个上界是安全的）。采用闭区间写法 while (left <= right)，可行时 right = mid - 1 继续向左找更小的，不可行时 left = mid + 1。循环结束时 left 恰好停在最小的可行值上——因为不变量始终是「left 左侧全部不可行，right 右侧全部可行」，两指针交错时 left 就是分界点。

解题步骤

确定二分区间：left = 0，right = sum(time)。为什么下界是 0：m >= n 时每天一题全部求助掉，代价为 0，这是真实可达的最小值。为什么上界取总和：一天做完时代价是 sum - max <= sum，所以 sum 一定可行，取它当右端安全且不会溢出。

闭区间二分：while (left <= right)，mid = left + (right - left) / 2。为什么这样算中点：直接写 (left + right) / 2 在两端都接近整型上限时会溢出；本题的量级虽不会溢出，但这是应该固化的习惯。

可行则收缩右边界：canFinish(mid) 为真时 right = mid - 1。为什么不是 right = mid：闭区间写法里 mid 已经检查过，保留它会导致区间不收缩甚至死循环。

不可行则抬高左边界：left = mid + 1，因为 mid 及更小的值都不可能可行。

返回 left：循环退出时 left = right + 1，且不变量保证 left 是最小的可行值。为什么不返回 right：right 停在最大的不可行值上，差一个。

判定函数的初始化：days = 1（第一天从一开始就存在，不是 0）、sum = 0、maxVal = 0。为什么 days 从 1 起：即使一道题都不换天，也要占用一天；从 0 起会让最终天数少算一天。

逐题累加并检查：先 sum += t、maxVal = max(maxVal, t)，再判断 sum - maxVal > limit。为什么先更新再判断：代价定义里的 max 必须包含刚加入的这道题，否则会低估或高估当前段的真实代价。

超限则开新一天：days++，若 days > m 立刻返回 false（提前退出，不必扫完）；否则重置 sum = t、maxVal = t。为什么重置成这道题而不是清零：这道题被推到了新的一天，它是新段的首个元素。

扫完返回 true：说明用不超过 m 天就能完成。

以 time = [1, 2, 3, 3]、m = 2 走一遍（预期答案 3）。总和为 9，二分区间是 [0, 9]。
第一次 mid = 4。判定：days = 1；加 1 得 sum=1, max=1，代价 0，不超；加 2 得 sum=3, max=2，代价 1，不超；加 3 得 sum=6, max=3，代价 3，不超；加第二个 3 得 sum=9, max=3，代价 6 > 4，开新一天，days = 2 不超过 m，重置为 sum=3, max=3。扫完返回 true。可行，right = 3。
第二次 left=0, right=3，mid = 1。判定：加 1 代价 0；加 2 代价 1，不超；加 3 得代价 3 > 1，开新一天，days=2，重置为 sum=3,max=3；加第二个 3 得 sum=6, max=3，代价 3 > 1，再开新一天，days=3 > 2，返回 false。不可行，left = 2。
第三次 left=2, right=3，mid = 2。判定：加 1、加 2 后代价 1 不超；加 3 得代价 3 > 2，开第二天，重置为 sum=3,max=3；加第二个 3 得代价 3 > 2，要开第三天，days=3 > 2，返回 false。left = 3。
第四次 left=3, right=3，mid = 3。判定：加 1、2、3 后 sum=6, max=3，代价 3，不超（等于上限，允许）；加第二个 3 得 sum=9, max=3，代价 6 > 3，开第二天，days=2，重置为 sum=3,max=3。扫完返回 true。right = 2，循环结束。
返回 left = 3，与预期一致。对应安排：第一天做前三题（求助掉耗时 3 的那道，实际 1+2=3），第二天做最后一题（求助掉，实际 0），最大值是 3。

再看 time = [999, 999, 999]、m = 4：m 大于题目数，判定任何 T >= 0 时每天单独做一题、代价全为 0，days = 3 <= 4，所以 canFinish(0) 为真，二分一路收缩到 left = 0。返回 0，正确。

代码实现

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)$，其中 S 是所有耗时之和。凭什么：二分区间长度为 S，每次折半，迭代次数为 $\log S$（约 30 次）；每次判定线性扫一遍数组，每个元素只做常数次加法、比较与赋值。代入约束是 $10^5 \times 30 = 3 \times 10^6$。

空间复杂度：$O(1)$。凭什么：二分与判定都只用了 left、right、mid、days、sum、maxVal 等标量，没有复制数组也没有开前缀和或 DP 表。

关键点总结

「最小化最大值」「最大化最小值」加上「可行性随参数单调」，就是二分答案的触发条件。先把最优化问题改写成判定问题，是这类题的第一步，也是最关键的一步。

判定函数的贪心要能论证：上限固定时每段尽量长，用到的段数一定最少。凡是二分答案，判定里的贪心都要给出这样一句「取到最优」的理由，否则二分建立在错误的判定上。

「每段可免掉一个元素」的代价模型应立刻化简成 sum - max，并想清楚免最大的那个最优。把代价写成闭式表达，扫描时才能 $O(1)$ 维护。

分段扫描超限时要把当前元素重置为新段的首元素，而不是清零后重新读——这是所有「贪心分段」题的共同细节。

闭区间二分的收敛写法是 left = mid + 1 与 right = mid - 1，退出时 left 是最小可行值。这套写法要背下来并理解不变量，比每次现推更可靠。

面试视角：先说清 DP 为什么不可行（$O(n^2 m)$），再点明单调性并给出二分框架，最后详细讲判定函数里 sum - max 的由来与贪心的正确性。面试官最想听判定函数的正确性论证；若被追问返回 left 还是 right，就用「循环退出时 left = right + 1，且 left 左侧全不可行」这句不变量回答。

易错点总结

错误写法：days 初始化为 0 → 用例 time = [1,2,3,3]、m = 2 中天数整体少算一，canFinish(1) 被误判为真，答案从 3 变成更小的值。

错误写法：判定时先比较再更新 maxVal → 用例 time = [1,2,3,3]、limit = 3 中加入第二个 3 时用的是旧的 max，代价算成 9 - 3 = 6 尚且正确，但若某段的新元素恰是最大值（如 [1,5]），代价会算成 6 - 1 = 5 而不是 6 - 5 = 1，判定过严，答案偏大。

错误写法：超限后把 sum 与 maxVal 清零而不是设为当前元素 → 用例 time = [1,2,3,3] 中被挤出的那道题凭空消失，后面段的代价被低估，答案偏小。

错误写法：代价写成 sum 而忘记减去 max → 用例 time = [999,999,999]、m = 4 中每天代价被算成 999，答案从 0 变成 999。

错误写法：判定条件写成 sum - maxVal >= limit → 用例 time = [1,2,3,3] 中代价恰好等于上限 3 的合法方案被拒，答案从 3 变成 4。

错误写法：可行时写 right = mid 且循环条件仍是 left <= right → 用例中区间不再收缩，left 与 right 卡在相邻两值上死循环。

错误写法：不可行时写 left = mid → 同样导致区间无法收缩，mid 反复取到同一个值。

错误写法：返回 right 而不是 left → 用例 time = [1,2,3,3]、m = 2 中返回 2，正好差一，因为 right 停在最大的不可行值上。

错误写法：二分右端取 max(time) 而不是 sum(time) → 用例 time = [1,2,3,3]、m = 1 中真实答案是 9 - 3 = 6，超出了右端 3，二分区间不含答案，返回错误值。

错误写法：二分左端取 min(time) 或 1 → 用例 time = [999,999,999]、m = 4 中答案是 0，被排除在区间之外，返回 1。

错误写法：中点写成 (left + right) / 2 且值域接近整型上限 → 本题量级安全，但在同型题（如上界取 $10^9$ 以上）中会溢出成负数，二分立刻失控。

错误写法：判定时不在 days > m 处提前返回，扫完再比较 → 逻辑仍正确但白白多扫剩余元素；更危险的是若把 days 累加写在错误的分支里，晚返回会掩盖问题。

错误写法：认为每天求助可以免掉「任意题」甚至跨天累积求助次数 → 用例 time = [1,2,3,3]、m = 2 中若允许两次求助集中在同一天，答案会算成 1，与题面「每天至多一次」不符。

相似题目

题目	难度	考察点
410. 分割数组的最大值	困难	同为连续分段最小化最大段和，但没有「免掉最大元素」这一层代价化简
1011. 在 D 天内送达包裹的能力	中等	判定逻辑几乎相同，但段代价就是纯和，二分下界必须取单件最大重量
875. 爱吃香蕉的珂珂	中等	二分速度而非代价上限，判定里用向上取整累加小时数，不涉及分段
1482. 制作 m 束花所需的最少天数	中等	二分天数，判定是统计连续可用花朵段数，需处理无解返回 -1
1552. 两球之间的磁力	中等	最大化最小间距，二分方向相反，收缩条件与返回值都要镜像过来
1231. 分享巧克力	困难	也是最大化最小段和，且段数固定为 `k + 1`，判定里贪心切分的终止条件不同
774. 最小化去加油站的最大距离	困难	答案是实数，二分要按精度而非整数收敛，判定里用除法算需要的加油站数
69. x 的平方根	简单	二分答案最基础的形态，判定就是一次乘法比较，用于熟悉边界收敛写法