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

题目大意是说，要求找到一个长度大于等于$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;
    }
}