鱼C论坛

 找回密码
 立即注册
查看: 3676|回复: 50

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

[复制链接]
发表于 2020-2-20 21:26:13 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
今天的题目:


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

给出 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 的木头。


欢迎大家一起答题!
最佳答案
2020-4-18 09:15:09
本帖最后由 kinkon 于 2020-4-18 09:49 编辑

经历一段学习,终于能按要求完成,二分法
  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
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 贡献 +3 收起 理由
LuckyTiger66 + 3 + 3 + 3 鱼C有你更精彩^_^

查看全部评分

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-2-25 15:24:58 | 显示全部楼层
大家会超时的输入数据:

testdata.zip (180.29 KB, 下载次数: 8)
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-20 21:40:43 | 显示全部楼层
程序员秒变建筑师,用代码修房子
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-20 21:49:06 | 显示全部楼层

看清楚题意,不能拼接,你这个只有2个长度4的木头,别人要求3个木头才行
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-20 22:15:51 | 显示全部楼层
本帖最后由 fan1993423 于 2020-2-20 22:30 编辑
  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])
复制代码

这下看还有没有问题

评分

参与人数 1荣誉 +2 鱼币 +2 收起 理由
zltzlt + 2 + 2

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-20 22:22:31 | 显示全部楼层
如果給m = 3, woods = [3, 10]是不是就無解
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-20 22:25:16 | 显示全部楼层
wcshds 发表于 2020-2-20 22:22
如果給m = 3, woods = [3, 10]是不是就無解

就是3塞
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-20 22:30:21 | 显示全部楼层
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))

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

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2020-2-20 22:34:50 | 显示全部楼层
这道题可以增加难度,给出len(woods)段可能有相同长度的木头
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-20 22:40:52 | 显示全部楼层
  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
复制代码


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

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-20 22:54:03 From FishC Mobile | 显示全部楼层
本帖最后由 拉了盏灯 于 2020-2-20 23:02 编辑

如果把木头劈成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荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-20 22:57:18 | 显示全部楼层
大家的答案都看不懂,这个需要学到哪一步才能写出来呀
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-20 23:00:18 | 显示全部楼层
  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
复制代码

暂时没想到别的

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-21 00:28:12 | 显示全部楼层
  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))
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-21 00:55:02 | 显示全部楼层
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

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-21 08:54:27 | 显示全部楼层
看不懂啊,有没有简单一点的题?
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-21 12:36:15 | 显示全部楼层
糕糕 发表于 2020-2-20 22:57
大家的答案都看不懂,这个需要学到哪一步才能写出来呀

我也是,他们的算法我都看不懂
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-21 14:49:02 | 显示全部楼层
看了三遍才看懂题 ,不过难度不大
  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
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-21 16:20:02 | 显示全部楼层

不行,不能拼接,没有3根长度4的木头
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-21 16:52:45 | 显示全部楼层
哈哈想了半天没想出正常的解法,因为这个有点复杂,他可能会出现【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]))

评分

参与人数 1荣誉 +2 鱼币 +2 收起 理由
zltzlt + 2 + 2

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-21 21:15:30 From FishC Mobile | 显示全部楼层
先把列表中最小的值,赋给最终结果;然后将列表中各个值,对刚才结果加1,分别求地板除后再求和,如果求和值大于等于列表的长度,就将其值赋给最终结果,否则舍弃;重复第二步直到列表中最大值。
缺点是求出来的结果是整数米,如果是小数呢?
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-7 11:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表