最佳牛围栏 —— 二分 + 前缀和

题目大意是说，要求找到一个长度大于等于 $F$ 的子段，使得这个子段内数字的平均值最大，求出这个最大值

解这道题分三步：

1. 首先二分答案，也就是平均值 $mid$
2. 用原数组 $A$ 减去平均值 $mid$，得到新数组 $B$，则问题转换为求 $B$ 中是否存在一个长度大于等于 $F$ 的子序列，使得子序列的和非负
3. 用双指针 $i,j$ 分别指向数组 $B$ 的前缀和数组 $S$，$i$ 从 $0$ 开始往后扫描，$j$ 永远与 $i$ 相隔 $F$ 长度，$i$ 在移动过程中不断记录最小值，然后判断 $sum [j]$ 是否大于等于这个最小值，如果大于，说明存在一个子序列和非负

import java.util.Scanner;

public class Main {
    static int[] arr = new int[100010];
    static double[] sum = new double[100010];
    static int n, f;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        f = cin.nextInt();
        arr = new int[n + 1];
        for (int i = 1; i <= n; i++)
            arr[i] = cin.nextInt();
        double l = 0.0, r = 2000;
        double eps = 1e-5;
        while (r - l > eps) {
            double mid = (l + r) / 2.0;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }
        System.out.println((int)(r * 1000));
    }
    static boolean check(double mid) {
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + arr[i] - mid;
        double min = 0;
        for (int i = 0, j = f; j <= n; i++, j++) {
            min = Math.min(min, sum[i]);
            if (sum[j] >= min)
                return true;
        }
        return false;
    }
}