袋子里最少数目的球

难度: Medium

给你一个整数数组 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⁵
1 <= maxOperations, nums[i] <= 10⁹

Submission

运行时间: 505 ms

内存: 27.5 MB

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        #袋子里的球是上取整还是下取整？
        #low是？
        #这种套路就是找到(或者自己写一个)target,然后必有题目里给的什么东西，
        #和target有关系式，然后target求和后一般<=题里给的东西
        right = max(nums) 
        left = 1#保证袋子里有球
       
        def check(y: int) -> bool:
            
            yopt = 0
            for n in nums:
              yopt += (n-1) // y
            return yopt <= maxOperations
        

        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid 
            else:
                left = mid + 1
        
        return left

Explain

本题解采用的是二分查找方法，来寻找能够最小化最大球数的开销。定义了一个辅助函数check(y)，用来确定是否可以通过最多maxOperations次操作将所有的球袋调整到每袋不超过y个球。在check函数中，计算每个球袋分裂成至多y个球的袋子所需的操作次数，并累加。如果这个总次数不超过maxOperations，返回True，表示可以实现。通过调整二分查找的范围（left, right），不断缩小可能的最大球数y，直到找到最小可能的y值，此值即为所求的最小化开销。

时间复杂度: O(n log(max(nums)))

空间复杂度: O(1)

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        right = max(nums)  # 最大的球数
        left = 1  # 最小的可能结果

        def check(y: int) -> bool:
            ops_needed = 0  # 需要的操作数
            for n in nums:
                ops_needed += (n - 1) // y  # 计算将每个袋子分裂至每袋不超过y个球需要的操作次数
            return ops_needed <= maxOperations  # 检查总操作数是否不超过允许的最大操作次数

        while left < right:  # 二分查找最小的可能的最大球数
            mid = (left + right) // 2
            if check(mid):
                right = mid  # 可以实现，尝试更小的值
            else:
                left = mid + 1  # 不能实现，需要更大的值

        return left  # 返回最终的最小可能值

Explore

算法选择二分查找是因为问题可以转化为确定性的判定问题："是否存在一个最大球数y，使得在给定的操作数内可以将所有球袋调整至每袋不超过y个球"。这个问题的答案具有单调性，即如果某个y可以实现，则y以上的值都可以实现；如果某个y不可以实现，则y以下的值都不可以实现。这使得二分查找成为有效的解决策略。相比之下，贪心策略可能在某些步骤做出局部最优选择，在全局上并非最优。动态规划则会面临较大的状态空间和复杂度问题，不适合处理这种范围搜索问题。

左边界left设为1，因为在最极端的情况下，每个球袋最少可以只包含1个球。右边界right设为max(nums)，即球袋中最多球的数量，因为在不进行任何操作的情况下，最大的球袋数目就是这个值。设定这样的初始边界是为了确保搜索范围涵盖所有可能的解。

公式`ops_needed += (n - 1) // y`用于计算将一个包含n个球的球袋分裂为每袋不超过y个球所需的操作次数。将一个袋子分裂成多个袋子时，每次操作可以从中取出至多y个球形成新袋子。因此，如果一个袋子有n个球，它至少需要`(n - 1) // y`次操作来确保每个新袋子里不超过y个球（除了最后一个可能少于y个球的袋子）。这个公式实际上是计算除了最后一个袋子外，每个袋子需要多少次分裂操作。

在Python中，使用`(left + right) // 2`来计算mid是安全的，因为Python的整数类型是动态的，可以根据需要自动扩展以防止溢出。这与一些其他语言（如Java或C++）不同，它们在处理大整数时可能会遇到溢出问题。在这些语言中，可能需要使用`left + (right - left) // 2`来避免潜在的整数溢出。