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

fan1993423 发表于 2020-2-20 22:15
这下看还有没有问题

解答错误

输入：m = 5, woods = [1, 1, 1, 1, 1, 2, 2, 2]
输出：2
预期结果：1

zltzlt

ruokang 发表于 2020-2-20 22:30
def f336(woods, m):
    max_hight = sum(woods) // m
    hight = max_hight

输入大数据超时

zltzlt

546623863 发表于 2020-2-20 22:40
目前么得其他思路，只有这个比较蠢的

输入大数据超时

zltzlt

拉了盏灯 发表于 2020-2-20 22:54
如果把木头劈成10/3还能高点，

输入大数据超时

zltzlt

塔利班 发表于 2020-2-20 23:00
暂时没想到别的

会超时

zltzlt

ouyunfu 发表于 2020-2-21 00:28

会超时

zltzlt

fan1993423 发表于 2020-2-22 21:16
你题目说的是不同长度的木头哈

我意思是不是全部都相同

zltzlt

TJBEST 发表于 2020-2-25 10:11
题主怎么不给试了？我答案当天给的，就测到我那里，

拖了好几天了今天测完

zltzlt

TJBEST 发表于 2020-2-21 14:49
看了三遍才看懂题 ，不过难度不大

会超时

zltzlt

我爱学习. 发表于 2020-2-21 16:52
哈哈想了半天没想出正常的解法，因为这个有点复杂，他可能会出现【5，60，100】这样的情况，这就不单单是一 ...

输入 m = 3, woods = [2, 3, 4] 没有返回值

zltzlt

kinkon 发表于 2020-2-21 23:24
想了好久才理清思路，感觉有些难度

会超时

zltzlt

牧木学编程 发表于 2020-2-22 00:03

返回值不能是小数哈

zltzlt

阴阳神万物主 发表于 2020-2-22 00:48
暴力破解，暂未想到更便捷的方案。

会超时

zltzlt

大家会超时的输入数据：

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

2020-2-25 15:24 上传

点击文件名下载附件

zltzlt

kinkon 发表于 2020-4-18 09:15
经历一段学习，终于能按要求完成，二分法

251 ms