使用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个球，即惩罚。

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

定义一个帮助函数helper()。这将获取target、mx
如果目标与0相同，则
- 返回mx + 1
计数:=0
对于nums中的每个数字，执行以下操作
- 计数 := count + (num – 1) / target的商
返回计数≤mx
从主方法中执行以下操作
left:=（nums所有元素之和/（nums大小+mx）的商和1的最大值）
right:= nums的最大值
while left
- 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))