农夫约翰的农场由 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
在本题中，相当于给出了一个序列，求一个平均数最大，长度大于等于f的一个子串。所以要用前缀和来计算字段的和。 运用二分法进行解决，首先要写一个判断函数，因为要用二分法求一个子串的长度。
int check(double mid) { for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]-mid; double minv=0; for(int i=0,j=f;j<=n;i++,j++) { minv=min(minv,sum[i]); if(sum[j]>=minv) return true; } return false; }所以要判断mid的值， sum[i]=sum[i-1]+a[i]-mid;在计算前缀和的时候，要把每一个值减去mid，这样就直接判断是否存在一个前缀和实现sum[j]-sumi>=0;如果大于零就会证明结果会比mid更大。
#include <bits/stdc++.h> using namespace std; const int N =100010;int n,f; int a[N];double sum[N]; int check(double mid) { for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]-mid; double minv=0; for(int i=0,j=f;j<=n;i++,j++) { minv=min(minv,sum[i]); if(sum[j]>=minv) return true; } return false; } int main() { scanf("%d%d",&n,&f); 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; if(check(mid)) l=mid; else r=mid; } printf("%d\n",int (r*1000)); return 0; }