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。

  • 如果target等于0，则

    • 返回mx + 1

  • count := 0

  • 对于nums中的每个num，执行：

    • count := count + (num - 1) / target 的商

  • 返回count <= mx

  • 在主方法中，执行以下操作：

  • left := max((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))

输入

[4,8,16,4], 4

输出

4

更新于：2021年10月6日

406 次浏览

启动你的职业生涯

完成课程获得认证

开始
广告