1760. 袋子里最少数目的球¶
难度：中等
题目¶
给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。
你可以进行如下操作至多 maxOperations 次：
- 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
- 比方说，一个袋子里有
5个球，你可以把它们分到两个新袋子里，分别有1个和4个球，或者分别有2个和3个球。
- 比方说，一个袋子里有
你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。
请你返回进行上述操作后的最小开销。
示例 1：
输入：
nums = [9], maxOperations = 2输出：
3解释：
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。
示例 2：
输入：
nums = [2,4,8,2], maxOperations = 4输出：
2解释：
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。
示例 3：
输入：
nums = [7,17], maxOperations = 2输出：
7
提示：
1 <= nums.length <= 10^51 <= maxOperations, nums[i] <= 10^9
题解¶
设nums数组的最大值为maxNum，则球数的最大值（即开销）limit显然落在区间[1, maxNum]内。随着limit的增大，所需要的划分次数单调减小。因此，可以使用二分查找的思路，给定一个开销limit，判断要使得分割后的数组最大值不高于该开销所需要的分割次数。
对于每个数值\(x\)，要将其分割为不超过\(y\)的数，所需要的分割次数等于分割后数字的数量\(\color{red}-1\)，即
\[
\left\lceil\frac{x \color{red} - 1}{y}\right\rceil
\]
维护一个区间(lo, hi]，每次检查中点\(med = \frac{lo + hi + 1}{2}\)，将区间划分为(lo, med]和(med, hi]。
- 如果所需的划分次数
numOperations大于要求的划分次数maxOperations，说明med的数值偏小，正确结果落在(med, hi]区间内。 - 否则，正确结果落在
(lo, med]区间内。
class Solution:
def countOperations(self, nums: List[int], cost: int):
return sum(map(lambda x: (x - 1) // cost, nums))
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
lo, hi = 0, max(nums)
while lo < hi - 1:
med = (lo + hi + 1) >> 1
numOperations = self.countOperations(nums, med)
if numOperations <= maxOperations:
hi = med
else:
lo = med
return hi