[已解决]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

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

1. def f336(m,woods):   
   
2.     if m <= 0 or not woods:
   
3.         return 0
   
4.     left, right = min(woods), sum(woods) // m   
   
5.     nds = lambda mid: sum(wood // mid for wood in woods) >= m
   
6.     while left + 1 < right:
   
7.         mid = left + (right - left)//2        
   
8.         if nds(mid):
   
9.             left = mid
   
10.         else:
    
11.             right = mid
    
12.     if nds(right):
    
13.         return right
    
14.     elif nds(left):
    
15.         return left
    
16.     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

1. from bisect import bisect
   
2. def fun336(m,woods):
   
3.     if not len(woods):return 0
   
4.     elif m==1:return max(woods)
   
5.     woods.sort()
   
6.     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

1. def fun336(m : int, woods : list):
   
2.     woods.sort(reverse = True)
   
3.     Max = 1
   
4.     for i in range(1,woods[0]+1):
   
5.         num = 0
   
6.         for each in woods:
   
7.             if(each >= i):
   
8.                 num += (each // i)
   
9.                 if(num >= m):
   
10.                     Max = i
    
11.                     break
    
12.             else:
    
13.                 return Max
    
14.     return Max

复制代码

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

拉了盏灯

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

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

复制代码

糕糕

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

塔利班

1. def f336(m,woods):
   
2.     if not woods:
   
3.         return 0
   
4.     n=max(max(woods)//m,1)
   
5.     while sum(e//n for e in woods)>=m:
   
6.         n+=1
   
7.     return n-1

复制代码

暂时没想到别的

ouyunfu

1. def f336(woods:list,m:int)->int:
   
2.     h=sum(woods)//m
   
3.     while True:
   
4.         n=0
   
5.         for i in woods:
   
6.             n+=i//h
   
7.         if n<m:
   
8.             h=h-1
   
9.         else:
   
10.             return h
    
11. print(f336([2, 3, 4],3))
    
12. 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

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

1. def fun336(m,woods):
   
2.     SortedWoods = sorted(woods)
   
3.     SortedWoods.reverse()
   
4.    
   
5.     M = len(woods)
   
6.     Count = 0
   
7.     MaxPossible = SortedWoods[0]
   
8.     for temp in range(MaxPossible,0,-1):
   
9.         for eachwood in SortedWoods:
   
10.             if eachwood < temp:
    
11.                 break
    
12.             else:
    
13.                 Count += eachwood // temp
    
14.                 if Count >= m:
    
15.                     return temp
    
16.                 else:
    
17.                     pass
    
18.         Count = 0
    
19.     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，分别求地板除后再求和，如果求和值大于等于列表的长度，就将其值赋给最终结果，否则舍弃；重复第二步直到列表中最大值。
缺点是求出来的结果是整数米，如果是小数呢？