『题解』A345.数列分段

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define re return
#define ew 5005
#define sz 10000005
#define sscc cout<<6;
const int MOD=1e9+7;
int n,m;
int num;
int a[sz];
bool check(int x){
	int fenzu=0;
	int sum=1;
	for(int i=1;i<=n;i++){
		if(a[i]>x){
			re false;
		}
		if(fenzu+a[i]<=x){
		 	fenzu+=a[i];
		}
		else{
			sum++;
			fenzu=a[i];
		}
	}
	re sum<=m;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		num+=a[i];
	}
	int l=0;
	int r=num+1;
	while(l+1<r){
		int mid=(l+r)/2;
		if(check(mid)){
			r=mid;
		}
		else{
			l=mid;
		}
	}
	cout<<r;
	re 0;
}