思路(二分+前缀和)

• 为什么使用二分?
• 我们要找的是平均数，平均数一定是[1,2000]
• 那么其实我们只需要从小到大或者从大倒下来枚举每一个平均数看是否满足要求即可(单调)
• 所以我们可以使用二分来找这个平均数
• 本题的关键在于check(mid)怎么写
• 首先我们明确这个mid就是我们要找的平均数，那么怎么判断这个平均数是否满足要求呢?
• 回到题意，要求的是每一段>=F的区间内的最大平均数
• 所以该区间内所有数都会大于等于我们的平均数，那么就是[l,r]都-mid后的和大于等于0
• 我们用前缀和sum[i]来记录前i个数减掉mid后的值
• 那么要求的就是sum[r]-sum[l-1]>=0,r-l+1 >=F就说明这个mid满足要求,满足要求就令l=mid
• 题目要求区间长度大于等于F，那么我们用双指针来保证区间长度大于等于F
• 题目要求最优解，那么就是要让sum[l-1]小的同时让sum[r]尽量大
• 所以我们用一个minv来记录sum[i]的最小值,如果sum[j] - minv >= 0 就保证这段一定满足题意

时间复杂度(二分O(log2000),check(O(F)[F最大为n])–>O(n*log2000)

import java.io.*;
import java.util.*;

public class Main{
    private static int N = 100010;
    private static int n,f;
    private static int[] a = new int[N];
    private static double[] sum = new double[N];
    private static boolean 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 ; j++,i++){
            minv = Math.min(minv,sum[i]);
            if(sum[j] >= minv){
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args)throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split("\\s+");
        n = Integer.valueOf(s[0]);
        f = Integer.valueOf(s[1]);
        for(int i = 1 ; i <= n ; i++){
            s = in.readLine().split("\\s+");
            a[i] = Integer.valueOf(s[0]);
        }
        double l = 0,r = 2000;
        while(r - l > 1e-6){
            double mid = (l + r)/2;
            if(check(mid)){
                l = mid;
            }else{
                r = mid;
            }
        }
        int ans = (int) (r * 1000);
        System.out.println(ans);
    }
}