1760.袋子里最少数目的球
binary search, https://leetcode.cn/problems/minimum-limit-of-balls-in-a-bag/
给你一个整数数组 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
class Solution:
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
def can_achieve(threshold):
operations = 0
for num in nums:
if num > threshold:
# 计算将num分成不超过threshold需要的操作次数
operations += (num - 1) // threshold
return operations <= maxOperations
left, right = 1, max(nums) + 1
ans = 0
while left < right:
mid = (left + right) // 2
if can_achieve(mid):
ans = mid
right = mid
else:
left = mid + 1
return ans思路：一开始想的不是二分 思路是正着平均拆分最大数 题解的二分法有一点逆向思维的意思 先选定一个数为最大值的最小值 再用maxOperations来判断指针变化。
from typing import List
class Solution:
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
left, right, ans = 1, max(nums) + 1, 0
while left < right:
y = (left + right) // 2
ops = sum((x - 1) // y for x in nums)
if ops <= maxOperations:
ans = y
right = y
else:
left = y + 1
return ans
if __name__ == "__main__":
sol = Solution()
print(sol.minimumSize([9], 2)) # expect 3
print(sol.minimumSize([2, 4, 8, 2], 4)) # expect 2为什么 left == right 是结束条件？
我们使用二分查找来寻找最小的最大球数 min_penalty，在 check(mid) 里只是在检查 mid 是否可行，而不是要恰好用掉 maxOperations。
operations == maxOperations并不意味着是最优解，因为可能存在更小的mid也满足operations <= maxOperations。left == right表示我们已经收敛到最小的可行mid，即满足operations <= maxOperations且不能再更小。
from typing import List
class Solution:
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
# 边界情况处理
if len(nums) == 1:
return (nums[0] + maxOperations) // (maxOperations + 1)
def check(n):
"""检查是否可以通过不超过maxOperations次操作将所有数分割为不大于n的块"""
operations_needed = 0
for num in nums:
# 计算需要的操作次数以确保每个数字被分割成最多为n的部分
operations_needed += (num - 1) // n
if operations_needed > maxOperations:
return False
return True
# 初始化二分查找的边界
left, right = 1, max(nums)
while left < right:
mid = (left + right) // 2
if check(mid):
right = mid
else:
left = mid + 1
return left题意解读
「最小化最大值」说人话就是，尽量均匀地分配小球。
思路
假设最终每个袋子的球数都至多为 m，那么 m 越小，操作次数就越多，m 越大，操作次数就越少，有单调性，可以二分答案。或者说，看到「最小化最大值」就要先思考二分。
现在问题变成：
根据您提供的图片文字信息，以下是提取的内容：
给定 m ，要求最终每个袋子的球数都至多为 m ，能否在 $ \text{maxOperations} $次操作内完成？
对于 $x = \text{nums}[i] $，假设分成 k 个袋子，每个袋子都至多装 m 个球。 k 不能太小，否则没法一共装 x 个球，所以 km 至少要是 x ，即
$ km \geq x $
解得
$ k \geq \left\lceil \frac{x}{m} \right\rceil $
所以对于 x ，操作次数为
$ \left\lceil \frac{x}{m} \right\rceil - 1 $
减一是因为操作 1 次分出 2 个袋子，操作 2 次分出 3 个袋子……依此类推，操作 k-1 次分出 k 个袋子。
累加操作次数，判断总操作次数与 $ \text{maxOperations} $ 的大小关系。
细节
下面代码采用闭区间。
- 左端点初始值：1。每个袋子的球数至少是 1。
- 右端点初始值：$ \max(\text{nums}) $。
关于上取整的计算，当 ( a ) 和 ( b ) 均为正整数时，我们有
$ \left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a-1}{b} \right\rfloor + 1 $
讨论 a 被 b 整除，和不被 b 整除两种情况，可以证明上式的正确性。
所以有
$ \left\lceil \frac{x}{m} \right\rceil - 1 = \left\lfloor \frac{x-1}{m} \right\rfloor $