CJBS06｜分批处理任务 题解

核心算法

二分最小的最大批次工作量；检查时按顺序贪心装入当前批次。

思路推导

给定上限 $C$，从左到右把任务尽量放入当前批次；若再放一个就超过 $C$，才开启新批次。这样得到的批次数最少。若最少批次数不超过 $m$，则可以继续拆分某些批次得到恰好 $m$ 个非空批次，因此 $C$ 可行。

可行性随 $C$ 增大呈“假到真”。答案下界是最大单个工作量，上界是所有工作量之和。

正确性说明

固定 $C$ 时，贪心让每个批次尽量向右延伸，因此它关闭第 $j$ 个批次的位置不会早于任何其他合法划分，使用的批次数最少。于是 groups<=m 当且仅当存在不超过 $m$ 批的划分。由于 $m\le n$ 且每项为正，少于 $m$ 批时总能继续拆成恰好 $m$ 个非空批次而不增加最大和。二分得到最小可行上限。

复杂度

• 每次检查：$O(n)$；
• 二分次数：$O(\log\sum a_i)$；
• 总时间：$O(n\log\sum a_i)$；
• 额外空间：$O(1)$。

易错点

• 批次必须连续，不能排序任务；
• 下界至少是 max(a[i])，上界是总和；
• 超过上限时当前任务应成为新批次的第一个；
• groups<=m 才可行，不必强求检查过程正好产生 $m$ 批；
• 所有和都用 long long。