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

更新于: 2021年10月18日

1K+ 阅读量

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告