YBTOJ:数列分段

题目大意

把一个长度为n数列分成m段,让每段的最大值最小。(m<=n)

题目分析

首先看出这题应该用二分做,然后考虑这道题答案范围的上下限:下限就是最大的\(a_i\),而上限就是\(\Sigma^{i=n}_{i=1}a_i\)
确定边界之后,开始二分:
用当前的mid作为每一段的最大值,假如能够将该数列分为m段,那么r=mid,那么r=mid,否则l=mid+1;

#include<iostream>
#include<cstdio>
#define sco 100010
using namespace std;
int n,m,l(0),r(0),a[sco];
bool check(int t){
	int sum=0,cnt=1;
	for(int i=1;i<=n;++i){
		if(sum+a[i]<=t)sum+=a[i];
		else {sum=a[i];++cnt;}
	}
	return cnt<=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)) r=mid;else l=mid+1;
	}
	printf("%d",l);
	return 0;
}

YBTOJ:数列分段

上一篇:MyBatis传参 # 和 $ 的区别


下一篇:22:卷积