洛谷P1182-数列分段（详解）

题目

给定一个长度为n的数列A，要求将它分为m段，要求每段连续，且每段和的最大值最小。N<=10e5,m<=n,Ai之和不超过10e9。

这题一看就知道我不会。所以很老实的去看了看题解。题解也真是避重就轻，重要的地方就说：这个要自己思考一下……

好吧，还好有代码。讲讲我自己的理解。

首先这个数字最大值一定存在（既然存在那一定找得到，即使有时候错过了，最后也还是会找回来。这个题是贪心+二分。先上代码，

    #include<iostream>
    using namespace std;
    typedef long long ll;
    int n, m;
    ll q[100002];
    ll sum;
    ll maxn;
    int l, r;
    int res = 0, cnt = 1;  //每个段的总和以及被分的段的总数
    inline bool check(int mid) {
        for (int i = 0;i < n;i++) {
            if (res + q[i] <= mid) res += q[i];
            else { res = q[i];cnt++; }
        }
        return cnt > m;     //重点
    }
    
    int main() {
        cin >> n >> m;
        for (int i = 0;i < n;i++) {
            cin >> q[i];
            if (maxn < q[i]) maxn = q[i];
            sum += q[i];
        }
        l = maxn;r = sum;
        while (l <= r) {
            res = 0;cnt = 1;
            int mid = (l + r) / 2;
            if (check(mid)) l = mid + 1;
            else r = mid - 1;
        }
        cout << l;
        return 0;
    }

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

首先考虑要寻找的答案，即最小的段最大值。它一定介于这个数列的最大值和整个数列和之间。因为数列中的最大值在被分段时，它所在的段和一定>=它，临界条件是=它，如果只要分一段，那自然是总和。

这段代码的check函数是重点，用二分法来寻找这个最小的最大和，mid用来判断与要求的数的方位。它里面对数列a进行分段，求每段的总和。要求分的段数必须是m，所以我用cnt来标记它被分的段数。在未经分段的时候，cnt初始化1，代表一整个数列一段。最后的return cnt>m的意思是：

1. 如果分段数目比要求的数目多（每段和<=mid），即代表这个mid选小了，目标数在它的左边，返回为1->执行左区间变化为mid+1。
2. 如果分段数目比要求的数目少，即代表这个mid太大了（每个段的数据多），目标数在它的右边，返回0->执行右区间变化mid-1。
3. 如果刚好等于呢？也并不能说就找到了答案，因为要求段和最大值最小，就必须贪心到最小，要往左边看看是否有更小的满足条件，所以变化左区间，与1一样。（当然也有可能就是要找的答案，这步还是会执行，但是答案不会有问题，顶多多几步操作）