【每日一题20220721】裁木料

兴趣爱好交流 每日一题
1

: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

题目难度：一般
题目来源：https://www.codewars.com/kata/583dbc028bbc0446f500032b


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
2 
wood_cut([232, 124, 456], 20) == 38. 这里应该是wood_cut([232, 124, 456], 21) == 38。
3

就是20

image
image823×279 21.3 KB

4

先ac再优化

image
image1853×917 69.7 KB

5 
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
6 
def wood_cut(woods: list , n: int) -> int:
    avg=sum(woods)//n
    print(avg)
    woods.sort(reverse=False)
    print(woods)
    while avg > 0:
        if sum([i // avg for i in woods]) >= n:
            return avg
        avg = max(i // ((i // avg) + 1) for i in woods)
    return avg

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