Python程式：查詢相同長度的k條絲帶的最大長度

假設我們有一個正數列表，表示絲帶的長度，還有一個值k。我們可以根據需要多次切割絲帶，我們需要找到最大的長度r，使得我們可以得到k條長度為r的絲帶。如果我們找不到這樣的解，則返回-1。

所以，如果輸入類似於 ribbons = [1, 2, 5, 7, 15] k = 5，那麼輸出將是5，因為我們可以將長度為15的絲帶切割成3段長度為5的絲帶。然後將長度為7的絲帶切割成長度為2和5的絲帶。還有一個長度為5的絲帶，所以我們總共得到了5條長度為5的絲帶。

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

• left := 0
• right := ribbons中的最大值
• 當 left < right 時，執行以下操作：
  • mid := floor of (left + right + 1) / 2
  • 如果列表中所有元素的總和（包含 (對於ribbons中每個至少為k的ribbonLen，ribbonLen / mid 的向下取整)）至少為k，則：
    • left := mid
  • 否則：
    • right := mid - 1
• 如果 left 不為零，則：
  • 返回 left
• 返回 -1

示例

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

def solve(ribbons, k):
   left = 0
   right = max(ribbons)
   while left < right:
      mid = (left + right + 1) // 2
      if sum((ribbonLen // mid for ribbonLen in ribbons)) >= k:
         left = mid
      else:
         right = mid - 1
   if left:
      return left
   return -1

ribbons = [1, 2, 5, 7, 15]
k = 5
print(solve(ribbons, k))

輸入

[1, 2, 5, 7, 15], 5

輸出

5

Arnab Chakraborty

更新於: 2021年10月18日

1K+ 閱讀量

開啟你的 職業生涯

透過完成課程獲得認證

立即開始