题解

考虑用二分查找求解。

下界为最小的元素（单开一段最小大小），上界为所有元素之和（所有元素在一段）。

使用solve函数判断当前期望的最小段是否可以达到：

• 当前段元素之和+当前元素<=x：当前段可以容纳a[i]而不破坏期望最大值，累计当前段元素之和。
• 当前段元素之和+当前元素>x：当前段不能容纳a[i]而不破坏期望最大值，将当前段元素之和重置为a[i]，并将段数++。

注意段落是cnt是从1开始累加的，因为最小的段数为1。

二分逻辑：由于返回true的情况可能包含正确答案，而返回true执行的操作为r=mid-1，因此最终答案为++r。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+5;

ll n,m,a[N],MIN,MAX;

bool solve(ll x){
    int now=0,cnt=1;
    for(ll i=1;i<=n;i++){
        if(now+a[i]<=x){
            now+=a[i];
        }else{
            now=a[i];
            cnt++;
        }
    }
    if(cnt<=m) return true;
    else return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        MIN=max(MIN,a[i]);
        MAX+=a[i];
    }

    ll l=MIN,r=MAX,mid;
    while(l<=r){
        mid=(l+r)/2;
        bool flag=solve(mid);

        if(flag==true) r=mid-1;
        else l=mid+1;
    }

    cout<<++r;

    return 0;
}