用 Python 编写程序，找出 k 条长度相同的丝带的最大长度

pythonserver side programmingprogramming更新于 2026/1/18 14:04:17

假设我们有一个正数列表，表示丝带长度，还有一个值 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 := 丝带的最大数量
while left < right，则执行
- mid := floor of (left + right + 1) / 2
- 如果列表中所有元素的总和包含 (floor ofribbonLen / mid for eachribbonLen inribbons that at least 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))