(算法进阶指南）102. 最佳牛围栏（最大平均数）

解题报告：二分平均值，由于他限定要不小于l长度的平均值，我们可以用个数组记录a[i]减去二分的平均值，如果最大的连续子序列长度大于等于0就l=mid ,由于是浮点数，eps设置为保留位数+2就行了，这题就是5.同时最后要乘以1000，l和r都是满足题意的，因为是最大值用r来*1000下取整就行了，接下来要找最大长度大于等于连续子序列的和，可以i从l开始循环，记录一下i-l前缀和和min，最后每次用前缀和i-min来更新ans就行了。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const	int N=1e5+10;
 double a[N];
 double sum[N];
 double b[N];
int n ,L;
bool	check(double mid)
{
   
	 double minv= 1e10;
	 double maxv=-1e10;
	for(int i=L;i<=n;i++)
	{
   
	minv = min(minv,sum[i-L]);
	maxv = max(maxv, sum[i]-minv);
	}
	return maxv>=0;
}
int main()
{
   

	cin >> n >> L;
	for(int i=1;i<=n;i++)
	cin >> a[i];
	 double l =0 , r = 2000;
	 while(r-l>1e-5)
	 {
   
		double mid =(l+r)/2;
		for(int i=1;i<=n;i++)
			b[i] =a[i] - mid;
		for(int i=1;i<=n;i++)
		sum[i] = sum[i-1] + b[i];	 	
		if(check(mid))
		l = mid;
		else
		r=mid;
	 }
	 printf("%d\n",(int)((l+r)/2*1000));// 二分实数，取上界(当精确度小于题目精确度的时候L可以的时候R也必定可以,取大故取R) 
    return 0;
}