[Acwing] 102围栏 二分答案+前缀和处理

前言

显然,二分答案 传送门:

思路

如何判断是否大于或者小于答案呢 ？

我们可以用前缀和处理 s [ i ] = s [ i − 1 ] + a [ i ] − m i d s[i] = s[i-1]+a[i]-mid s[i]=s[i−1]+a[i]−mid

为了满足答案经可能大,所以我们需要在左端点找一个最小值 如果对于该最小值 存在合法区间 那么我们就令 l = m i d l = mid l=mid

CODE

void solve()
{
	cin>>n>>f;
	
	double l = 0 ,r = 0 ;
	
	for(int i = 1;i>a[i];
		r = max(a[i],r);
	}
	
	while(r - l > 1e-5)
	{
		double mid =  (l+r)/2;
		
		for(int i=1;i