在Python中查找具有相同长度的k个带子的最大长度的程序

在Python中查找具有相同长度的k个带子的最大长度的程序

假设我们有一个表示带子长度的正数列表,还有一个值k。我们可以任意切割彩带,我们必须找到最大长度r,使我们可以有k个长度为r的带子。如果我们找不到这样的解决方法,则返回-1。

所以,如果输入是彩带= [1,2,5,7,15] k = 5,那么输出将为5,因为我们可以将大小为15的带子切成3段,每段长度为5。然后将大小为7的带子切割成2和5。还有另一根长为5的带子,因此我们总共得到5个长度为5的带子。

要解决此问题,我们将遵循以下步骤-

  • 左:= 0
  • 右:=彩带的最大值
  • 当左 < 右时,执行以下操作
    • 中:=(左+右+1)// 2的floor值
    • 如果在列表中的所有元素的总和中包含(至少为k的每个彩带的ribbonLen / mid的菜单),则
      • 左:= mid
    • 否则,
      • 右:= mid-1
  • 如果左不为零,则
    • 返回左侧
  • 返回-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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程