数列分段

解题思路

设最优解为mid，如果每段和都小于mid
则一定存在一种最优解
段数不超过m
否则就提高mid

AC代码

#include<cstdio>
#include<algorithm> 
using namespace std;
int n,m,l,r,a[100005];
bool check(int x)//判断
{
   
	int sum=0,num=1;//sum为当前段的和，num为分了多少段
	for(int i=1;i<=n;i++)
	 if(sum+a[i]>x)
	 {
   
	 	num++;
		sum=a[i];
		if(a[i]>x)return 0;//记得特判，如果当前点已经大于，就无法分段
	 }
	 else sum+=a[i];
	return num>m; 
}
int main()
{
   
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
   
		scanf("%d",&a[i]);
		l=max(l,a[i]); //找最大值
		r+=a[i];//和
	}
	while(l<r)//二分
	{
   
		int mid=(l+r)/2;
		if(check(mid))l=mid+1;
		else r=mid;
	}
	printf("%d",l); 
	return 0;
}

谢谢