https://www.luogu.com.cn/problem/P1182

我第一次的代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],l,r=1e9,mid,ans;
bool check(int x){
    int tot=0,num=0;
	for(int i=1;i<=n;i++){
        if(tot+a[i]<=x)tot+=a[i];
        else tot=a[i],num++;
    }
    return num<=m;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
		l=max(l,a[i]);
		
	}
    while(l+1<r){//这是我们老师推荐的二分模板,但是交上去20分
		int mid=(l+r)/2;
		if(check(mid)==1){
			r=mid;
		}
		else{
			l=mid;
		}
	}
	cout<<l<<endl;
}

第二次的代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],l,r=1e9,mid,ans;
bool check(int x){
    int tot=0,num=0;
  	for(int i=1;i<=n;i++){
        if(tot+a[i]<=x)tot+=a[i];
        else tot=a[i],num++;
    }
    return num>=m;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
		l=max(l,a[i]);
	}
    while(l<=r){//这是另一个二分模板
        mid=(l+r)/2;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<l<<endl;
}