【每日一题20220721】裁木料

:mage:‍给了一些木头。它由一个整数数组woods (参数1)给出,每个元素是木头的长度。将它们切成小块,以保证您可以拥有等于或多于n (参数 2)具有相同长度的块(长度应该是整数)。你的任务是找出你能从这些树林中得到的最长长度是多少?返回小块的最大长度。

一个例子:

woods = [232, 124, 456], n = 7
我们拥有的木头长度分别是232,124,456,需要裁成7份同长度的木头,要求尽可能的长,结果应该是114,因为 232 可以裁成2段114长度的木头,剩余4(可以丢弃),124可以裁一段剩余10,456可以裁成4段无剩余。裁出来的数量是 2+1+4 = 7段,如果我们裁成115则最多只能裁出6段一样长的。

注意:

  • 中的所有数字woods 都是正整数;
  • n 也是一个正整数;
  • 结果应该是整数长度的小块,尽可能长;
  • 请注意优化代码避免超时

一些例子

woodCut([232, 124, 456], 7) === 114
woodCut([232, 124, 456], 20) === 38
woodCut([232, 124, 456], 1) === 456
woodCut([232, 124, 456], 2) === 232
woodCut([232, 124, 456], 3) === 228
woodCut([1, 1, 1], 4) === 0
woodCut([1, 1, 1], 3) === 1

题目难度:一般
题目来源:Wood Cut | Codewars


def wood_cut(woods: list , n: int) -> int:
    pass

assert wood_cut([232, 124, 456], 7) == 114
assert wood_cut([232, 124, 456], 20) == 38
assert wood_cut([232, 124, 456], 1) == 456
assert wood_cut([232, 124, 456], 2) == 232
assert wood_cut([232, 124, 456], 3) == 228
assert wood_cut([1, 1, 1], 4) == 0
assert wood_cut([1, 1, 1], 3) == 1
assert wood_cut([200000000, 2147483645, 2147483646, 2147483647], 4) == 1073741823
assert wood_cut([2000000000, 2147483645, 2147483646, 2147483647], 4) == 2000000000
wood_cut([232, 124, 456], 20) == 38. 这里应该是wood_cut([232, 124, 456], 21) == 38。

就是20

先ac再优化

def wood_cut(woods, n):
    if sum(woods)//n == 0:
        return 0
    max_ln=sum(woods)//n
    while max_ln>0:
        if sum([i//max_ln for i in woods])  >= n:
            return max_ln
        max_ln = max(i//((i//max_ln) + 1) for i in woods)
    return max_ln
关闭