在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