数列分段

对于给定的一个长度为 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）

输出：

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

样例：

1
2
3
4
5
6
5 3
4
2
4
5
1
1
6

1.思路

image-20211011181323769

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
using namespace std;

long long n, m, num[100005], rawl, rawr;

long long func(long long x) {
    long long t = 0, now = 0;
    for (int i = 0; i < n; ++i) {
        if (now + num[i] > x) {
            t++;
            now = num[i];
        } else if (now + num[i] == x) {
            t++;
            now = 0;
        } else {
            now += num[i];
        }
    }
    if (now != 0) {
        t++;
    }
    return t;
}

long long bs() {
    long long l = rawl, r = rawr;
    while(l != r) {
        long long mid = (l + r) / 2;
        long long s = func(mid);
        if (s <= m) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return r;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        rawl = max(rawl, num[i]);
        rawr += num[i];
    }
    cout << bs() << endl;
    return 0;
}