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

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 上传

点击文件名下载附件

hy324

厉害了，哈哈

kinkon

终于弄了个分钟能跑完超长数据的准确程序，累死宝宝了...

kinkon

解题如下

kinkon

引用了外部模块，解楼主给的超长数据，自己测试，时长8秒

import numpy as np
def p336(m,woods):
    woods1 = np.sort(np.array(woods))[-m:][::-1]
    lmin, pmax = max(woods) // m, sum(woods) // m
    if woods1.size <= 1:
        return lmin
    if m == 1:
        return max(woods)        
    nwoods = np.unique(woods1)[::-1]
    t = k = rec = 0
    while k < nwoods.size:        
        t += 1                           
        tmp, c = nwoods[k]//t, 0        
        if lmin <= tmp <= pmax:
            if tmp > rec:                
                c = np.sum(woods1//tmp)              
            else:
                k += 1
                t = 0                        
            if c >= m: 
                rec = max(rec, tmp)                
                k += 1
                t = 0
        else:
            if t == m:
                k += 1  
    return rec

kinkon

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

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

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

251 ms