[已解决]Python：每日一题 336

zltzlt

今天的题目：

假设你是建造寺庙的建筑师。寺庙的柱子是由木头制成，每根柱子必须是一节完整的木头而且不能是被连接得到的。

给出 len(woods) 段具有不同长度的木头。你的寺庙有 m 根高度严格相同的柱子。求寺庙的最大高度。

示例 1：

输入：m = 3, woods = [2, 3, 4]
输出：2
解释：选择长度为 2 的木头并且长度为 4 的木头被分为两段长度为 2 的木头。

示例 2：

输入：m = 3, woods = [2, 10]
输出：3
解释：长度为 10 的木头分为 3 段长度为 3 的木头和一根长度为 1 的木头。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

kinkon

2020-4-18 09:15:09

经历一段学习，终于能按要求完成，二分法

def f336(m,woods):    

    if m <= 0 or not woods:

        return 0

    left, right = min(woods), sum(woods) // m   

    nds = lambda mid: sum(wood // mid for wood in woods) >= m

    while left + 1 < right:

        mid = left + (right - left)//2        

        if nds(mid):

            left = mid

        else:

            right = mid

    if nds(right):

        return right

    elif nds(left):

        return left

    return 0

跳转到最佳答案楼层

zltzlt

大家会超时的输入数据：

testdata.zip (180.29 KB, 下载次数: 8)

2020-2-25 15:24 上传

点击文件名下载附件

fan1993423

程序员秒变建筑师，用代码修房子

fan1993423

一个账号 发表于 2020-2-20 21:38
这样行不行：

看清楚题意，不能拼接，你这个只有2个长度4的木头，别人要求3个木头才行

fan1993423

from bisect import bisect
def fun336(m,woods):
    if not len(woods):return 0
    elif m==1:return max(woods)
    woods.sort()
    return max(woods[-1]//m,woods[bisect(woods[:-1],woods[-1]//(m-1))-1])

这下看还有没有问题

wcshds

如果給m = 3, woods = [3, 10]是不是就無解

fan1993423

wcshds 发表于 2020-2-20 22:22
如果給m = 3, woods = [3, 10]是不是就無解

就是3塞

ruokang

def f336(woods, m):
    max_hight = sum(woods) // m
    hight = max_hight
    while (hight != 0):
        num = 0
        for wood in woods:
            num += wood // hight
        if num >= m:
            break
        else:
            hight -= 1
    return hight

m = 3
woods = [2, 10]
print(f336(woods, m))

不知道有没有问题，测试结果是对的
我不知道怎么弄成代码框的样子

fan1993423

这道题可以增加难度，给出len(woods)段可能有相同长度的木头

546623863

def fun336(m : int, woods : list):
    woods.sort(reverse = True)
    Max = 1
    for i in range(1,woods[0]+1):
        num = 0
        for each in woods:
            if(each >= i):
                num += (each // i)
                if(num >= m):
                    Max = i
                    break
            else:
                return Max
    return Max

目前么得其他思路，只有这个比较蠢的

拉了盏灯

如果把木头劈成10/3还能高点，

def fc336(m,woods):
        for i in range(max(woods),0,-1):
                if m<=woods.count(i):
                        return i
                elif m <= len([h for e in sorted(woods)[::-1] if e//i != 0 or e==i for h in [i]*(e//i)]):
                        return i
        return 0

糕糕

大家的答案都看不懂，这个需要学到哪一步才能写出来呀

塔利班

def f336(m,woods):
    if not woods:
        return 0
    n=max(max(woods)//m,1)
    while sum(e//n for e in woods)>=m:
        n+=1
    return n-1

暂时没想到别的

ouyunfu

def f336(woods:list,m:int)->int:
    h=sum(woods)//m
    while True:
        n=0
        for i in woods:
            n+=i//h
        if n<m:
            h=h-1
        else:
            return h
print(f336([2, 3, 4],3))
print(f336([2, 10],3))

whosyourdaddy

def func336(m,woods):
    woods.sort()
    length = 1
    result = 0
    while length < woods[-1]:
        num = 0
        for each in woods:
            num += each // length
        if num >= m:
            result = length
        length += 1
    return result

scwcha

看不懂啊，有没有简单一点的题？

一个账号

糕糕 发表于 2020-2-20 22:57
大家的答案都看不懂，这个需要学到哪一步才能写出来呀

我也是，他们的算法我都看不懂

TJBEST

看了三遍才看懂题 ，不过难度不大

def fun336(m,woods):
    SortedWoods = sorted(woods)
    SortedWoods.reverse()
    
    M = len(woods)
    Count = 0
    MaxPossible = SortedWoods[0]
    for temp in range(MaxPossible,0,-1):
        for eachwood in SortedWoods:
            if eachwood < temp:
                break
            else:
                Count += eachwood // temp
                if Count >= m:
                    return temp
                else:
                    pass
        Count = 0
    return 0

w932861108

一个账号 发表于 2020-2-20 21:38
这样行不行：

不行，不能拼接，没有3根长度4的木头

我爱学习.

哈哈想了半天没想出正常的解法，因为这个有点复杂，他可能会出现【5，60，100】这样的情况，这就不单单是一个木头切开就行了，它可以取100的两截木头，60的一截木头，所以就只好笨笨的从最大的高度开始试......只是这样只能是整数高度的。
def fun(number,woods):
    woods.sort(reverse=True)#从大到小排列
    for hight in range(woods[0],woods[-1],-1):
        num=0   #第几根木头
        wood_copy=woods[:]
        for i in range(0,number):   #试试是否能凑满number根指定高度（hight）的木头
            if hight > wood_copy[num]:
                if num == len(woods)-1 or hight>wood_copy[num+1]:   #凑不齐，跳出循环，换下一个hight
                    break
                else:
                    num+=1
            wood_copy[num]-=hight
        else:#木头凑齐了
            return hight




print(fun(3,[2,3,100,100]))

liuaihua1984

先把列表中最小的值，赋给最终结果；然后将列表中各个值，对刚才结果加1，分别求地板除后再求和，如果求和值大于等于列表的长度，就将其值赋给最终结果，否则舍弃；重复第二步直到列表中最大值。
缺点是求出来的结果是整数米，如果是小数呢？