用Python查找袋子中球的最小限制的程序

假设我们有一个数组 nums，其中第 i 个元素表示一个包含 nums[i] 个球的袋子。我们还有另一个值叫做 mx。我们最多可以执行以下操作 mx 次 -

• 选择任意一袋球，将其分成至少有一个球的两个新袋子。

• 这里的惩罚是一个袋子里的最大球数。

我们必须尽量减少手术后的惩罚。所以最后，我们必须在执行操作后找到最小可能的惩罚。

因此，如果输入像 nums = [4,8,16,4], mx = 4，那么输出将是 4，因为我们可以执行以下操作： 最初我们有像 [4,8,16,4] 这样的包, 分袋 16 个球，如 [4,8,8,8,4]，然后对于每个袋子有 8 个球，将它们分成两个袋子，每个袋子各 4 个球，因此数组将像 [4,4,4, 8,8,4]，然后是 [4,4,4,4,4,8,4]，最后是 [4,4,4,4,4,4,4,4]，所以这里最少有 4 个球，这就是惩罚。

示例

让我们看看以下实现以获得更好的理解 -

def helper(target, mx):
   if target == 0:
      return mx + 1
   count = 0
   for num in nums:
      count += (num - 1) // 目标
   return count <= mx

def solve(nums, mx):
   left, right = max(sum(nums) // (len(nums) + mx), 1), max(nums)
   while left < right:
      mid = (left + right) // 2
      if helper(mid, mx):
         right = mid
      else:
         left = mid + 1
   return left

nums = [4,8,16,4]
mx = 4
print(solve(nums, mx))

输入

[4,8,16,4], 4

4