答主能力有限，表述可能存在一些问题或表述不清。请谅解也欢迎批评指正。如有错误，将第一时间改正。若能对刷题的你有一丝丝帮助，那将是我的荣幸。点点向上的小箭头，答主会很开心^▽^

题目描述

农夫约翰的农场由 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

初学者无法理解的点

1.为什么要用二分？二分的作用是什么？

首先我们要清楚这道题的答案是什么？

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

即本质就是平均值。

而又从题目第一行得知，

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

平均值肯定是在1到2000之间的。

所以既然我们知道找的是平均值，即找满足题目条件的平均值，我们可以设满足条件的值为x，即我们是在1到2000之间寻找这个x。

如此，用二分来寻找，加快速度。

而在这里是实数二分，故用对应的模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps    // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

2.check函数中，为什么每个数要减去mid？

首先我们要知道mid是什么？

mid就是我们二分找的数，通过mid，来定位满足条件的x。x是平均数，即mid的本质也就是平均数。

那么为什么要减去mid呢？见下面的例子

avg = (x1 + x2 + x3) / 3

x1 + x2 + x3 = 3 * avg = avg + avg + avg

(x1 - avg) + (x2 - avg) + (x3 - avg) = 0

通过上例可以发现，如果每个数减去avg等于0，那么这些数的平均值就为avg；若小于0，则平均值小于avg，大于0则平均值大于avg。

与此我们可以通过（x - mid） 的和来确定mid与平均值之间的关系，从而确定二分的方向。

3.check函数中下面的代码的作用？为什么要有一个min？

        for(int i = 0,j = F;j<=N;j++,i++){
            min = Math.min(min,sum[i]);
            if(sum[j] - min >= 0) return true;
        }
        return false;

（1）sum[i]是什么？这个是前缀和数组。（注意是每个数都减去了mid再求的前缀和）

（2）return true 说明了什么？ 平均数在mid的右边。反之在mid左边。

（3）for(int i = 0,j = F;j<=N; j+ +, i+ +) 保证 j - i >= F（这个是题目的要求）

（4）min = Math.min(min,sum[i]); 就是用来找到前i个数中最小的前缀和。

（5）if(sum[j] - min >= 0) return true;

字面解释：前j个数的前缀和减去前i个数中最小的前缀和 如果大于0，则平均数在mid的右边

原因：注意我们是去找到那个满足题目要求的平均值，只要找到它就好。
且先要知道 前j个数的前缀和减去前i个数的前缀和是什么东西？
即 (a1 + a2 +… + aj) - (a1 + a2 + … +ai) = a(i+1) + … + aj;
代入i为0，j为F模拟一下，得到的就是 a1 + a2 + … + aF（注意每个数都是减去了mid的）
如果它大于等于0，回到第二点中 如果每个数减去avg等于0，那么这些数的平均值就为avg；若小于0，则平均值小于avg，大于0则平均值大于avg。
说明平均值大于avg，也即大于mid，即平均数在mid右边，更新 l=mid。

那 前j个数的前缀和减去前i个数中最小的前缀和也迎刃而解了，减去最小的如果还小于0，那这个区间的平均值肯定小于mid，就要更新r=mid。

Java 代码

import java.io.*;

public class Main{
    static int N;
    static int F;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        N = Integer.parseInt(strs[0]);
        F = Integer.parseInt(strs[1]);
        double[] a = new double[N+10];
        double[] sum = new double[N+10];
        for(int i = 1 ; i <= N ; i++){
            strs = br.readLine().split(" ");
            a[i] = Integer.parseInt(strs[0]);
        }

        double l = 0;
        double r = 2000;
        while(r - l > 1e-5){
            double mid = (l + r) / 2 ;
            if(check(a,mid,sum)) l = mid;
            else r = mid ;
        }
        System.out.print((int)(r * 1000));
    }

    public static boolean check(double[] a,double mid,double[] sum){
        for (int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + a[i] - mid;
        }
        double min = 0;
        for(int i = 0,j = F;j<=N;j++,i++){
            min = Math.min(min,sum[i]);
            if(sum[j] - min >= 0) return true;
        }
        return false;
    }

}