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

Arnab Chakraborty

更新于：2021年10月18日

75 次浏览

开启您的职业生涯

完成课程获得认证

开始学习