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

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

点击文件名下载附件

hy324

厉害了，哈哈

kinkon

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

kinkon

解题如下

kinkon

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

1. import numpy as np
   
2. def p336(m,woods):
   
3.     woods1 = np.sort(np.array(woods))[-m:][::-1]
   
4.     lmin, pmax = max(woods) // m, sum(woods) // m
   
5.     if woods1.size <= 1:
   
6.         return lmin
   
7.     if m == 1:
   
8.         return max(woods)        
   
9.     nwoods = np.unique(woods1)[::-1]
   
10.     t = k = rec = 0
    
11.     while k < nwoods.size:        
    
12.         t += 1                           
    
13.         tmp, c = nwoods[k]//t, 0        
    
14.         if lmin <= tmp <= pmax:
    
15.             if tmp > rec:               
    
16.                 c = np.sum(woods1//tmp)              
    
17.             else:
    
18.                 k += 1
    
19.                 t = 0                        
    
20.             if c >= m:
    
21.                 rec = max(rec, tmp)               
    
22.                 k += 1
    
23.                 t = 0
    
24.         else:
    
25.             if t == m:
    
26.                 k += 1  
    
27.     return rec

复制代码

kinkon

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

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

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

251 ms