假设我们有一个正数列表,表示色带长度并且还有一个值 k。我们可以根据需要多次切割丝带,我们必须找到最大长度 r,这样我们可以有 k 条长度为 r 的丝带。如果我们找不到这样的解决方案,则返回-1。
因此,如果输入类似于色带 = [1, 2, 5, 7, 15] k = 5,那么输出将是 5,因为我们可以将大小为 15 的色带切成 3 条长度为 5 的条带。然后把7号的丝带剪成2号和5号。 还有另外一个5号的丝带,所以我们总共得到了5条5号的丝带。
让我们看看以下实现以获得更好的理解 -
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