Python程式：計算K小時內移除石頭的速率

假設我們有一個名為piles的數字列表和一個值k。piles[i]表示第i堆石頭數量。每小時，我們選擇任何一堆石頭並移除r塊石頭。如果我們選擇的一堆石頭少於r塊，仍然需要一小時才能清除該堆石頭。我們必須找到r的最小值，以便我們能夠在k小時或更短的時間內移除所有石頭。

因此，如果輸入類似於piles = [3, 6, 4] k = 5，則輸出將為3，因為對於每小時移除3塊石頭(r = 3)，我們可以用2小時清除第二堆，用2小時清除第三堆，用1小時清除第一堆。

為了解決這個問題，我們將遵循以下步驟：

  • l := 1
  • h := piles中的最大值
  • r := h
  • 定義一個函式turns()。這將需要r
  • 返回列表中所有元素的總和，其中(每個b在piles中，向上取整 b / r)
  • 在主方法中，執行以下操作：
  • 當l < h時，執行
    • mid := floor((l + h) / 2)
    • 如果turns(mid) > k，則
      • l := mid + 1
    • 否則，
      • h := mid
      • r := min(r, mid)
  • 返回r

示例

讓我們看看下面的實現以更好地理解：

from math import ceil
def solve(piles, k):
   l = 1
   h = max(piles)
   r = h

   def turns(r):
      return sum(ceil(b / r) for b in piles)
   while l < h:
      mid = (l + h) // 2
      if turns(mid) > k:
         l = mid + 1
      else:
         h = mid
         r = min(r, mid)
   return r

piles = [3, 6, 4]
k = 5
print(solve(piles, k))

輸入

[3, 6, 4], 5

輸出

3

更新於：2021年10月18日

75 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告