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

輸出

Arnab Chakraborty

更新於：2021年10月6日

406 次瀏覽

啟動你的職業生涯

完成課程獲得認證

開始