信息学奥赛一本通T1436-数列分段II - C语言网 (dotcpp.com)

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int N=1e5+100;
const int inf=1e9;
int n,m;
int a[N];
bool check(int mid)
{
    int sumn=0,pos=1,cnt=1;
    //sumn表示该区间的和，pos表示数组下标，cnt表示分了区间的个数
    while(pos<=n)
    {
        if(sumn+a[pos]>mid)//该区间的和已经符合要求
        {
            cnt++;
            sumn=0;
        }
        else
        {
            sumn+=a[pos];
            pos++;
        }
    }
    if(cnt<=m)
        return true;
    else
        return false;
}
signed main()
{
    cin>>n>>m;
    int l=-1,r=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        l=max(l,a[i]);r+=a[i];//缩小搜索区间
    }
    while(l<r)//二分答案，区间和的最大值的最小
    {
        int mid=(l+r)/2;
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }
    cout<<l;
    return 0;
}