[luogu] P1182 数列分段 Section II 二分答案

前言

很基础的一个二分答案( 但是还是WA了

传送门 :

思路

二分答案基本步骤 :

• 确定上下界
• 确定 c h e c k check check

我们先确定上下界 , 因为是和的最大值最小, 所以我们的 r = s u m ( a [ i ] ) r = sum(a[i]) r=sum(a[i]) 显然

但是我们的下界不能是从 1 1 1开始,为什么呢? 因为不管是分为一个单独的集合 还是

和其他集合再一团,我们的最小值都只可能是 m a x ( a [ i ] ) max(a[i]) max(a[i]) ,所以这就是上下界

然后我们确定 c h e c k check check , 既然确定是二分答案了,所以对于每一个区间和 大于

m i d mid mid 的我们就给它单独开一个区间,如果最后开的区间大于等于 m m m那么答案就

往那边递进,反之则然

CODE

bool check(int x)
{
	int cnt = 0 ; 
	int sum = 0 ;
	for(int i=1;ix){
			cnt++;
			sum = a[i] ;
		}else sum+=a[i];
	}
	
	if(cnt>= m )return true;
	else return false;
}
void solve()
{
	cin>>n>>m;
	int l = 1,r = 0 ;
	
	for(int i=1;i>a[i];
		r +=a[i];
		l = max(l,a[i]);
	}
	// cout