2600. 集装运输
1000ms
512MB
简单
题目描述
传送带上依次摆放着 `n` 件货物，第 `i` 件货物的重量为 `a_i`。
小 J 最多可以安排 `k` 辆货车来运输。每辆货车只能运送**连续的一段货物**，并且每件货物恰好由一辆货车运送。每辆货车可以不运货，也可以运送任意长度的一段。
一辆货车的载重压力等于它所运送货物的重量之和。小 J 希望**最重的那辆车的载重压力尽可能小**。
请你输出这个最小可能的值。
输入格式
第一行两个整数 `n, k`。
第二行 `n` 个整数 `a_1, a_2, ..., a_n`。
输出格式
输出一个整数，表示最重一辆车的载重压力的最小值。
样例 1
输入 (Input)
输出 (Output)
样例 2
输入 (Input)
输出 (Output)
样例说明
### 样例解释 1
分成 `[4,2,4]` 和 `[5,1]`，两辆车的载重压力分别为 `10` 和 `6`，最大值为 `10`。
其他分法的最大值都不小于 `10`，例如 `[4,2]` 和 `[4,5,1]` 的最大值也是 `10`，`[4]` 和 `[2,4,5,1]` 的最大值是 `12`。
- $1 <= k <= n <= 10^5$
- $1 <= a_i <= 10^9$
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功