g5-09154. 分天运输 未做

快递站要把 $n$ 箱货按录单顺序装车运走,计划用不超过 $days$ 天运完。货车每天装载的总重量不能超过上限 $cap$,一箱货不可拆分、不可调换次序,当天装不下就整箱留到下一天。请求出能按时运完的最小整数上限 $cap$。

第一行两个整数 $n,days$。
第二行 $n$ 个整数 $w_i$,按运输顺序给出各箱重量。

一行一个整数,表示最小的可行上限 $cap$。

试 $cap=8$:第一天装 $1+2+3=6$,再装 $4$ 就超;第二天装 $4$,再装 $5$ 到 $9$ 也超,需要第三天,超过 $2$ 天,不可行。试 $cap=9$:第一天 $1+2+3=6$,第二天 $4+5=9$,恰好两天运完。故最小 $cap$ 为 $9$。

$1\le days\le n\le 2\times 10^5$;$1\le w_i\le 10^9$。