数列分段 Section II

题目描述

对于给定的一个长度为 N 的正整数数列 A_1~N，现要将其分成 M（M <= N）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

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

将其如下分段：

[4 2] [4 5] [1]

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

将其如下分段：

[4] [2 4] [5 1]

第一段和为 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

提示

1 <= N <= 1e5, M <= N, A_i <= 1e8

思路

先找到区间最大和的范围（n-1个区间，1个区间），再判断符合区间最大和的条件下能分成多少个区间（用count表示），最后不断进行调整直到符合条件

代码实现

#include <iostream>

const int N = 1e5 + 10;
int a[N], sum, Max = 0, n, m;
using namespace std;

bool judge(int Sum);
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
        Max = a[i] > Max ? a[i] : Max;
    }
    //最大区间和的范围 Max ~ sum
    //Max -> 有n - 1段区间
    //sum -> 有1段区间
    int l = Max, r = sum;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(judge(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}
bool judge(int Sum)  //Sum定义为区间和的最大值
{
    int count = 0, ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(ans + a[i] <= Sum) ans += a[i];
        else
        {
            count++;
            ans = a[i];  //上段区间已经满了，进入一段新的区间
        }
    }
    //count > m  ->  区间过多，区间和小了，要在右边寻找Sum
    //count < m  ->  区间过少，区间和大了，要在左边寻找Sum
    return count < m;
}