解题思路
本题要求把长度为 L 的序列 w 划成恰好 k 段连续非空子段,使各段元素和的最大值(峰值负载 peak)最小。这是经典的 二分答案 + 贪心验证(与 LeetCode 410「分割数组的最大值」同型)。
- 单调性:若峰值上限 limit 可行,则任意更大的 limit 也可行;不可行则更小的 limit 也不可行。在 [max(w), ∑w] 上二分。
- 检验
can(limit):从左到右贪心累加当前段和,超过 limit 就新开一段;统计最少段数 cnt。若 cnt≤k,说明可在不超过 limit 的前提下拆成至多 k 段;因 k≤L 且每段非空,还可继续切到恰好 k 段而不增大峰值。
- 二分得到的最小可行 limit 即为最小 peak。
复杂度分析