数列分段.

题目描述
​ 对于给定的一个长度为 N 的正整数数列 Ai，现要将其分成 M(M≤N) 段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 4 2 4 5 1 要分成 3 段

将其如下分段：

[4 2][4 5][1]
第 1 段和为 6，第 2 段和为 9，第 3 段和为 1，和最大值为 9。

将其如下分段：

[4][2 4][5 1]
第 1 段和为 4，第 2 段和为 6，第 3 段和为 6，和最大值为 6。

并且无论如何分段，最大值不会小于 6。

所以可以得到，要将数列 4 2 4 5 1 分成 3 段，每段和的最大值最小为 6。

输入
​ 第一行两个整数 N,M。（1≤M≤N≤100,000）
​ 接下来 N 行，每行一个数，表示 Ai。（1≤Ai≤100,000,000）

输出
​ 一个正整数，即每段和最大值最小为多少。

样例输入

5 3
4
2
4
5
1

样例输出

6

数据规模与约定
​ 时间限制：1 s

​ 内存限制：256 M

​ 100% 的数据保证 1≤M≤N≤100,000，1≤Ai≤100,000,000

#include <iostream>
using namespace std;long long n, m, num[1000005], num_max, num_sum;
long long check(long long mid) {long long mmax = 0, cnt = 0;for (int i = 0; i < n; i++) {if (mmax + num[i] == mid) {cnt++;mmax = 0;}else if (mmax + num[i] > mid) {cnt++;mmax = num[i];}else {mmax += num[i];}}if (mmax > 0) {cnt++;}return cnt;
}
int main() {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> num[i];num_max = max(num_max, num[i]);num_sum += num[i];}long long l = num_max, r = num_sum;while (l != r) {long long mid = (l + r) / 2;long long s = check(mid);if (s > m) {l = mid + 1;}else {r = mid;}}cout << l << endl;return 0;
}