Leetcode1760：袋子里最少数目的球

题目描述：

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

• 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
  • 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

代码思路：

1. 初始化边界：
   • l（left）初始化为 1，因为最小的开销可以是 1（即每个袋子最多只有一个球）。
   • r（right）初始化为 max(nums)，因为不进行任何操作时，开销的最大值就是数组中的最大值。
2. 二分查找：
   • 使用二分查找在 [l, r] 范围内寻找满足条件的最小开销。
   • 每次计算中间值 mid 作为当前的候选开销。
3. 计算操作数：
   • 对于数组中的每个袋子 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）。
4. 调整边界：
   • 如果计算出的总操作数 op 大于 maxOperations，说明当前的 mid 作为开销太小，无法在给定的操作次数内完成，因此需要增大开销，将 l 更新为 mid+1。
   • 否则，当前的 mid 可能是一个可行的解（但不一定是最小的），因此尝试减小开销，将 r 更新为 mid（因为 mid 也可能是一个解，所以这里用 mid 而不是 mid-1 来更新 r，以确保不会错过 mid 这个可能的解）。
5. 返回结果：
   • 当 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)>>1
            if (op:=sum([ (x-1)//mid for x in nums]))>maxOperations:
                l=mid+1
            else:
                r=mid
        return l