P3308. 项目排期

解题思路

题目理解

又是一道描述相当晦涩的题目（很想骂人）。用比较简洁的数学语言来描述就是，将数组 X1, X2, X3, ... , Xm 分为 N 部分（并非子数组，不要求连续），设每一部分的和为 sum1, sum2, ..., sumN，要求找到一种分配方式使得 max(sum1, sum2, ..., sumN) 最小。

用一句简单的话来说，就是 最小化各部分求和的最大值。这种设问一定要想到用 二分 来完成。

问题转化

将问题转化为，我们需要找到一个阈值 k（一个人的最大工作量），并将原数组 nums 可以被分为 N 部分（分配给 N 个人），使得这 N 部分的各自求和的最大值都不会超过 k（每个人各自的工作量不会超过 k）。

显然 k 的选择是一个 二段性问题：

• 当 k 非常小时，原数组 nums 无论怎么分配都无法完成要求
• 当 k 非常大时，原数组 nums 无论如何分配都可以完成要求

必然存在一个 临界值 k，使得存在 nums 的分配结果恰好完成要求。

二分查找范围

我们希望找到这个阈值 k，因此需要对 k 进行二分查找，二分查找的范围为 [max(nums), sum(nums)]。当：

• k = max(nums) 时，能够被分为 m = len(nums) 部分（需要 m 个人来完成所有工作）
• k = sum(nums) 时，能够被分为 1 部分（只由 1 个人可以完成所有工作）

贪心子问题

而上述二分过程的 贪心子问题 为：当我们选择了阈值 k 时，数组 nums 能否被分割不超过 N 部分？

这个问题就和 【贪心】2023B-数据最节约的备份方法 几乎完全一致了，其代码为：

二分过程

初始化 左闭右开区间 left = max(nums)，right = sum(nums) + 1，进行二分。

计算 mid = (left + right) // 2。当：

• sub_question(mid, nums, m, N) 为 True 时，说明当选择了阈值 k = mid 时，可以将任务分配给 N 个人（组数小于等于 N）。此时的 mid 的选择偏大，区间应该左移，right 左移。
• sub_question(mid, nums, m, N) 为 False 时，说明当选择了阈值 k = mid 时，无法将任务分配给 N 个人（组数大于 N）。此时的 mid 的选择偏小，区间应该右移，left 右移。

故结合贪心子问题，整体的二分代码为：

复杂度分析 设 m 为需求个数（数组 nums 的长度），S 为所有需求工作量之和 sum(nums)。

• 预处理逆序排序为 O(m log m)，只做一次。
• 贪心子问题 sub_question：外层遍历每个尚未分配的需求，内层从位置 i 向后扫到数组末尾尝试把工作塞给当前员工，最坏情况下内外层各 O(m)，单次调用为 O(m^2)（代码注释中也标明了这一点）。
• 二分在区间 [max(nums), sum(nums)+1) 上进行，迭代 O(log S) 次，每轮调用一次 sub_question。

因此总时间复杂度为 O(m^2 log S)，瓶颈在贪心检查的双重循环。空间上每次检查会新建长度为 m 的 check 标记数组，空间复杂度为 O(m)。