P3302. 开放日活动

解题思路

二段性分析

考虑容量最大值 `maxCapacity` 与剩余小球数量之间的关系。

• 容量最大值 `maxCapacity` 越大的时候，在原列表 bucketBallNums 中需要取出的小球数越少，剩余小球数量越多。当取到最值 maxCapacity = max(bucketBallNums) 时，则无需取出任何小球，bucketBallNums 等同于初始状态，必然大于 `SUM`。
• 容量最大值 `maxCapacity` 越小的时候，在原列表 bucketBallNums 中需要取出的小球数越多，剩余小球数量越少。当取到最值 maxCapacity = 0 时，则需取出所有小球，此时剩余小球数量为 0，必定小于等于 `SUM`。

对于在区间 [0, max(bucketBallNums)] 之间取值的容量最大值 maxCapacity 而言，一定存在一个值 `ans`，使得：

• 当 maxCapacity ∈ [0, ans] 时，剩余球数小于等于 SUM
• 当 maxCapacity ∈ (ans, max(bucketBallNums)] 时，剩余球数大于 SUM

这体现了这个问题的二段性，ans 是我们需要的答案，而 ans 的寻找就可以用二分查找来完成。

边界情况的考虑

如果 sum(bucketBallNums) < SUM，那么无需设置容量最大值 `maxCapacity`，直接输出空列表 []。这种情况需要单独讨论。

二分查找的框架

子问题分析

对于二分查找过程中得到的每一个容量最大值 maxCapacity = mid，我们都要计算得到原数组 bucketBallNums 取出小球后的剩余球数。对于 bucketBallNums 中每一个元素 num，当：

• bucketBallNums[i] = num < maxCapacity 时，在 bucketBallNums[i] 中无需取出任何小球，故求和时应该用 num 进行求和
• bucketBallNums[i] = num ≥ maxCapacity 时，在 bucketBallNums[i] 中需要取出若干球，直到 num 变为 maxCapacity，故求和时应该用 maxCapacity 进行求和

上述逻辑整理为代码即构建 getSumWithMaxCap(maxCapacity, bucketBallNums) 函数：

复杂度分析 设 n 为小桶个数（数组 bucketBallNums 的长度），V 为桶中球数的最大值 max(bucketBallNums)。

• 开头对 bucketBallNums 求和判断是否需要取球，为 O(n)。
• getSumWithMaxCap 对数组做一趟遍历，累加每个桶的 min(num, maxCapacity)，单次调用为 O(n)。
• 二分查找在 [1, max(bucketBallNums)+1) 上进行，迭代 O(log V) 次，每轮调用一次 getSumWithMaxCap。
• 二分结束后按 maxCapacity 再扫一遍数组构建每个桶要取出的球数，为 O(n)。

因此总时间复杂度为 O(n log V)，瓶颈在二分内每一轮的整组求和。空间上除输入外，主要是长度为 n 的答案数组，空间复杂度为 O(n)。另外注意 C++ 版本用 long 存储球数与总和，避免 n 个桶求和时超出 int 范围。