用 Python 编写程序，查找袋子中球的最小数量

pythonserver side programmingprogramming更新于 2025/11/30 22:36:17

假设我们有一个数组 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 个球，这就是惩罚。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 helper() 。这将获取目标，mx
如果目标与 0 相同，则
- 返回 mx + 1
count := 0
对于 nums 中的每个数字，执行
- count := count + (num - 1)/target 的商
返回 count <= mx
从主方法，执行以下操作
left := (nums 所有元素之和 /(nums 的大小 + mx)) 和 1 的商的最大值
right := nums
当 left < right 时，执行
- mid := (left + right)/2 的商
- 如果 helper(mid, mx) 非零，则
  - right := mid
- 否则，
  - left := mid + 1
返回 left

示例

让我们看看下面的实现以便更好地理解 −

def helper(target, mx):
   if target == 0:
      return mx + 1
   count = 0
   for num in nums:
      count += (num - 1) // target
   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))