2394. 连续子数组和的最大值最小化
1000ms
256MB
简单
贪心算法
二分算法
题目描述
给定一个长度为 $N$ 的非负整数数组 $A$。现需要将该数组划分为 $M$ 个连续的子数组，要求每个元素都必须属于且仅属于一个子数组。
请计算并输出一种划分方案，使得这 $M$ 个连续子数组各自的元素之和的最大值达到最小。
输入格式
- 第一行包含两个正整数 $N$ 和 $M$ ($1 \le M \le N \le 10^5$)，分别表示数组的长度和需要划分的段数。
- 第二行包含 $N$ 个以空格隔开的非负整数 $A_i$ ($0 \le A_i < 10^8$)，代表数组的元素。
输出格式
- 输出一个正整数，表示每段和的最大值在最优划分下的最小值。
样例 1
输入 (Input)
5 3 4 2 4 5 1
输出 (Output)
6
样例说明
- **样例说明**：
将数组 `4 2 4 5 1` 划分为 3 段，最优划分方案为 $[4], [2, 4], [5, 1]$。
各段的和分别为 4、6、6，最大值为 6。可以证明不存在最大值小于 6 的更优划分方案，因此输出 6。
- 对于 $20\%$ 的数据：$N \le 10$。
- 对于 $40\%$ 的数据：$N \le 1000$。
- 对于 $100\%$ 的数据：$1 \le N \le 10^5$，$M \le N$，$0 \le A_i < 10^8$，最终答案不超过 $10^9$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功