题目描述:
给你一个整数数组 nums
,其中 nums[i]
表示第 i
个袋子里球的数目。同时给你一个整数 maxOperations
。
你可以进行如下操作至多 maxOperations
次:
- 选择任意一个袋子,并将袋子里的球分到 2 个新的袋子中,每个袋子里都有 正整数 个球。
- 比方说,一个袋子里有
5
个球,你可以把它们分到两个新袋子里,分别有1
个和4
个球,或者分别有2
个和3
个球。
- 比方说,一个袋子里有
你的开销是单个袋子里球数目的 最大值 ,你想要 最小化 开销。
请你返回进行上述操作后的最小开销。
代码思路:
- 初始化边界:
l
(left)初始化为 1,因为最小的开销可以是 1(即每个袋子最多只有一个球)。r
(right)初始化为max(nums)
,因为不进行任何操作时,开销的最大值就是数组中的最大值。
- 二分查找:
- 使用二分查找在
[l, r]
范围内寻找满足条件的最小开销。 - 每次计算中间值
mid
作为当前的候选开销。
- 使用二分查找在
- 计算操作数:
- 对于数组中的每个袋子
x
,计算将其球数分到不超过mid
的开销所需的操作数。 - 由于每次操作是将一个袋子分成两个袋子,并且每个袋子里的球数都是正整数,所以我们需要将
x
个球分到不超过mid
的两个袋子中。 - 最坏情况下,我们需要将
x
个球分到mid
和x-mid
(或ceil(x/2)
和floor(x/2)
,取决于x
是奇数还是偶数)两个袋子中,但因为我们只关心操作次数,所以只需要考虑将x
个球分到尽可能接近mid
的两个袋子中。 - 由于每次操作至少会减少一个袋子(因为我们把一个袋子分成了两个),所以我们可以将
x
个球分到不超过mid
的袋子中的操作次数近似为(x-1)//mid
(向下取整,因为每次操作减少一个球,直到剩余球数不超过mid
)。 - 注意这里的
(x-1)//mid
实际上是在计算将x
个球分到不超过mid
的袋子中,最多需要进行多少次“拆分”操作(每次操作至少减少一个袋子,但球的总数减少mid
或更少时,需要多次操作才能达到每个袋子不超过mid
)。
- 对于数组中的每个袋子
- 调整边界:
- 如果计算出的总操作数
op
大于maxOperations
,说明当前的mid
作为开销太小,无法在给定的操作次数内完成,因此需要增大开销,将l
更新为mid+1
。 - 否则,当前的
mid
可能是一个可行的解(但不一定是最小的),因此尝试减小开销,将r
更新为mid
(因为mid
也可能是一个解,所以这里用mid
而不是mid-1
来更新r
,以确保不会错过mid
这个可能的解)。
- 如果计算出的总操作数
- 返回结果:
- 当
l
和r
相等时,循环结束,此时l
(或r
)即为满足条件的最小开销。
- 当
代码实现:
class Solution:def minimumSize(self, nums: list[int], maxOperations: int) -> int:l,r=1,max(nums)while l<r:mid=(l+r)>>1if (op:=sum([ (x-1)//mid for x in nums]))>maxOperations:l=mid+1else:r=midreturn l