我爱学习. 发表于 2020-2-21 16:52
哈哈想了半天没想出正常的解法，因为这个有点复杂，他可能会出现【5，60，100】这样的情况，这就不单单是一 ...
输入 m = 3, woods = 没有返回值
kinkon 发表于 2020-2-21 23:24
想了好久才理清思路，感觉有些难度
会超时
牧木学编程 发表于 2020-2-22 00:03
返回值不能是小数哈
阴阳神万物主 发表于 2020-2-22 00:48
暴力破解，暂未想到更便捷的方案。
会超时
大家会超时的输入数据：
厉害了，哈哈
本帖最后由 kinkon 于 2020-3-3 18:14 编辑
终于弄了个分钟能跑完超长数据的准确程序，累死宝宝了...
本帖最后由 kinkon 于 2020-3-5 09:15 编辑
解题如下
引用了外部模块，解楼主给的超长数据，自己测试，时长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//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 于 2020-4-18 09:49 编辑
经历一段学习，终于能按要求完成，二分法
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
kinkon 发表于 2020-4-18 09:15
经历一段学习，终于能按要求完成，二分法
251 ms{:10_275:}