农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。

约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。

在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式
第一行输入整数 N 和 F ，数据间用空格隔开。

接下来 N 行，每行输入一个整数，第i+1行输入的整数代表第i片区域内包含的牛的数目。

输出格式
输出一个整数，表示平均值的最大值乘以1000再 向下取整 之后得到的结果。

数据范围
1≤N≤100000
1≤F≤N
输入样例：
10 6
6
4
2
10
3
8
5
9
4
1
输出样例：
6500

思路：num[]储存每块地的牛的数量
首先这个平均数一定是在0到num[]中最大的。然后对0到最大值进行二分查找。
由于结果会乘以1000，所以精度要求在0.0001。
二分查找的是这个平均数，查找的条件是：在>=F的区间内是否有平均值比当前平均数大的平均数
对于查找条件的实现。有一个巧妙的思维就是前缀和。
首先，利用num[i]-mid先处理数组，如果结果大于0，则表示这个数比平均数大，小于0则这个数比平均数小。
然后求出前缀和。sum[i]表示0~i之间的数的和。这个和是减去了i*mid的结果。
如果sum[i]大于0，则表示区间0~i的平均数比mid大。
由于题目要求的是大于等于F长度的区间。因此二重循环为

for(int i=0;i<=N-F;i++){
    for(int j=F;j<=N;j++){

    }
}

如果要优化到一重循环，可以设两个变量i=0,j=F,循环截止条件为j<=N.循环时i和j同时++。
这时，对于i到j之间的就是一个定长F的区间在从左到右。
对于0~i的处理，求出0~i之间的最小值。记为minv.
sum[j]-minv表示右边定点为j，左边点是值为minv的sum[i]中的i，这个区间的前缀和;也就是右边定点，左边点可以变。
为什么要求最小值呢？因为我们要用sum[j]-minv。如果minv是最小的那么sum[j]-minv就会是最大的。
如果sum[j]-minv大于0则表示在右边点是j的长度大于F的区间的平均数比mid大。

初始化时minv=0的原因：?

#include<iostream>

using namespace std;
const int N=100010;
int m;
double n;
double num[N];
double sum[N];
bool check(double mid){
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+(num[i]-mid);
    }
    double x=0;
    for(int i=0,j=m;j<=n;i++,j++){
        x=min(x,sum[i]);
        if(sum[j]-x>=0)return true;
    }
    return false;
}

int main(){
    cin>>n>>m;
    double l=0,r=0;
    for(int i=1;i<=n;i++){
        cin>>num[i];
        r=max(r,num[i]);
    }

    while(r-l>=1e-4){
        double mid=(l+r)/2;
        if(check(mid)){
            l=mid;
        }else{
            r=mid;
        }
    }
    cout<<(int)(r*1000)<<endl;
    return 0;
}