数列分段（二分）

[数列分段 Section II]

题目描述

对于给定的一个长度为 \(N\) 的正整数数列 \(A_{1\sim N}\)，现要将其分成 \(M\)（\(M\leq N\)）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 \(4\ 2\ 4\ 5\ 1\) 要分成 \(3\) 段。

将其如下分段：

第一段和为 \(6\)，第 \(2\) 段和为 \(9\)，第 \(3\) 段和为 \(1\)，和最大值为 \(9\)。

将其如下分段：

第一段和为 \(4\)，第 \(2\) 段和为 \(6\)，第 \(3\) 段和为 \(6\)，和最大值为 \(6\)。

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

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

输入格式

第 \(1\) 行包含两个正整数 \(N,M\)。

第 \(2\) 行包含 \(N\) 个空格隔开的非负整数 \(A_i\)，含义如题目所述。

输出格式

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

样例输入

5 3
4 2 4 5 1

样例输出

6

提示

对于 \(20\%\) 的数据，\(N\leq 10\)。

对于 \(40\%\) 的数据，\(N\leq 1000\)。

对于 \(100\%\) 的数据，\(1\leq N\leq 10^5\)，\(M\leq N\)，\(A_i < 10^8\)， 答案不超过 \(10^9\)。

#include <bits/stdc++.h>
using namespace std;

int main() 
{
    int n, m;
    scanf("%d%d", &n, &m);

    vector<int> a(n);
    int l = 0, r = 0;

    for (int i = 0; i < n; i++) //for (int i = 1; i <= n; i++)，会导致数组越界应该从 i = 0 开始遍历（会错过第一个元素 a[0]，并且在 i = n 时会访问到 a[n]，这会导致数组越界RE）
    {
        scanf("%d", &a[i]);
        l = max(l, a[i]);//更新l为数组中的最大值，r为数组所有元素的和
        r += a[i];
    }

    while (l < r)
    {
        int mid = l + (r - l) / 2;
        int sum = 0, baka = 1; //最后一段也需要计数

        for (int i = 0; i < n; i++) 
        {
            if (sum + a[i] > mid) 
            {
                sum = a[i];
                baka++;
            } else {
                sum += a[i];
            }
        }

        if (baka > m)
        {
            l = mid + 1; // 分段多，说明mid太小，增大l
        } else {
            r = mid;  //段数少，说明数太大，要改小一点
        }
    }

    printf("%d\n", l);

    return 0;
}

模板：

最大值最小（本题）

while(l<r)
{
    int mid=(l+r)>>1;
    if(check(mid))
        r=mid;
    else
        l=mid+1;
}

最小值最大

while(l<r)
{
    int mid=(l+r+1)>>1;
    if(check(mid))
        l=mid;
    else
        r=mid-1;
}