洛谷题单指南-二分查找与二分答案-P1182 数列分段 Section II

原题链接：https://www.luogu.com.cn/problem/P1182

题意解读：每段和的最大值越小，则分段数就越多，因此可以通过给定每段和的最大值，将分段数划分为两类：<=M，>M，对每段和的最大值进行二分即可。

解题思路：

二分的判定条件为，给定每段和的最大值，计算分段数，计算逻辑如下：

依次遍历每一个数，求当前数到开始数的区间和，

如果区间和大于每段和的最大值，则区间数+1，且当前数作为下一个区间的开始数

最终统计得到区间数，如果区间数<=M，说明符合条件，每段和的最大值可以往更小的进行探索，否则往更大的探索

100分代码：

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

const int N = 100005;

int a[N], n, m, ans;
long long s[N];

bool check(int x)
{
    int i = 1, last = 1, cnt = 1;
    while(i <= n)
    {
        if(s[i] - s[last - 1] > x)
        {
            last = i;
            cnt++;
        }
        i++;
    }
    return cnt <= m; //分段小于等于m，可以试探分段更多，分段越多，即最大分段和更小
}

int main()
{
    cin >> n >> m;
    int maxx = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i]; //s是前缀和数组
        maxx = max(maxx, a[i]); //记录最大值
    }

    int l = maxx, r = 1e9; //左边界至少是其中最大的数，即如果每个数一个分段，这时最大的分段和最小，为数列的最大数
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans;

    return 0;
}