注释删掉可以看二分过程

#include<iostream>
using namespace std;
int a[int(1e5)];
int n,m;
int main()
{
	cin >> n >> m;
	int maxn=0;
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
		maxn=max(maxn,a[i]);
	}
	long long l=maxn,r=int(1e8),mid;
	while(l<=r){
		mid=(l+r)/2;
		int sum=0,x=0;
		for (int i=0;i<n;i++){
			//cout << "dbg1:" << sum << " ";
			sum+=a[i]; 
			if (sum>mid){
				x++;
				sum=0;
				sum+=a[i]; 
			}else if(sum==mid){
				x++;
				sum=0;
			}
		}
		//cout  << endl;
		if(sum!=0)x++;
		//if(x>1)cout << "dbg1:" << l << " " << mid << " " << r << " " << x << endl;
		if (x<=m){
			r=mid-1;
		}else{
			l=mid+1;
		}
//		if(x>1){
//			cout << "dbg2:" << l << " " << mid << " " << r << " " << x << endl;
//			cout << endl;
//		}
		
	}
	cout << r+1;
}

题意

从一个n元素序列里分段至m段，使得其总和最大值得最小。

死路

直接从下往上枚

这样的时间复杂度为$C_{n-1}^{m-1}$。 即O(n!)。

思路

二分篇章，当然是二分解决呀！可以反其道而行之，用二分枚举总和最大值，然后对m调范围，而不是很多人先入为主，在m的框架里面搜索，这样根本做不出来。

代码

//欢迎借鉴
//本题第一位AC者的
//优质代码
#include<iostream>
#define int long long
using namespace std;
signed main(){
	int n,m;
	cin>>n>>m;
	int a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	int l=0,r=1e14;
	while(l<=r){
		int s=(l+r)>>1;
		bool check(int*,int,int,int);
		if(check(a,n,m,s))
			l=s+1;//二分范围
		else
			r=s-1;//二分范围
	}
	cout<<l;
}
bool check(int*a,int n,int m,int s){
	int m1=0,now=0;//m1是段数，now是用来存临时的计算结果。
	for(int i=0;i<n;i++){
		if(a[i]>s)//如果元素大于你的总和最大值
			return 1;//直接排除
		if(now+a[i]>s){
			m1++;
			now=a[i];
		}
		else
			now+=a[i];
	}
	return m1>=m;//对比m与段数
}

注意

由于上界的最大值为$1e5*1e8=1e13$，用int会爆掉，所以要用long long