蓝桥杯 算法提高 ADV-1164 和谐宿舍 python AC

贪心，二分

同类型题：蓝桥杯 算法提高 ADV-1175 打包

def judge(x):wood = 0max_val = 0ans_len = 0for i in ll:if i > x:return Falseelif max(max_val, i) * (ans_len + 1) <= x:max_val = max(max_val, i)ans_len += 1else:wood += 1max_val = ians_len = 1if ans_len:wood += 1return wood <= mn, m = map(int, input().split())
ll = list(map(int, input().split()))
l, r = 0, max(ll) * len(ll)
while l < r:mid = (l + r) // 2if judge(mid):r = midelse:l = mid + 1
print(l)

函数遍历中加入了一个剪枝，判断当单个画大于木板时直接返回false，否则代码会直接判断加入新元素后的大小