本题解来源于 p_868

SOLUTION

直接二分，贪心 check 即可。

具体地，check 时直接往后枚举，不能再加了就切一段下来，还不行就直接判不可能。

另外地，要分 $m$ 段，只能切 $m-1$ 刀，于是 m--。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m;
int a[101000];
int check(int mid){
    int now=0,cnt=0;
    for(int i=1;i<=n;i++){
        if(now+a[i]>mid) now=0,cnt++;
        now+=a[i];
        if(now>mid) return 0;
    }
    return cnt<=m;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;m--;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int L=0,R=1e9;
    while(L<R){
        int mid=(L+R)>>1;
        if(check(mid)) R=mid;
        else L=mid+1;
    }
    cout<<L<<'\n';
    return 0;
}