二分+前缀和/滑动窗口——成绩统计

题目分析：

定位关键词——“至少要检查多少个人的成绩，才有可能选出 k 名同学，他们的方差小于一个给定的值 T”，也就是满足条件的最小值，可以考虑用二分。但是他需要可以二分，也就是单调性或者二段性。每次选择都是选择前x个数，然后在这前x个数里面找到一组个数为k的数，他们的方差满足条件，如果x可以找到，那么x继续增大也可以找到，因为增大后的x是包含了增大前的x的。举个例子，假设x=5。在a[1],a[2],a[3],a[4],a[5]中，我们可以找到a[2],a[3],a[5]满足方差小于T，那么当x=8时，对于a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]也一定存在a[2],a[3],a[5]满足方差小于T，因此具有单调性，也就是小的值满足条件，大的值也一定满足条件。

接下来考虑二分过程。

第一阶段二段性分析

当我检查了前mid个同学的成绩之后，如果可以找到一组数，个数为k，且方差小于T，那么我会尝试找更小的值是不是也满足条件，所以向左边走，即

if (check(mid)) {r = mid;} //因为mid是符合条件的，所以我要留着它，而不是l=mid+1

当我检查了前mid个同学的成绩之后，如果不可以找到一组数，个数为k，且方差小于T，那么我只能找更大的值，所以向右边走，即

else { l = mid + 1; }//因为mid是不符合条件的，所以我不要留着它，而不是r=mid

综上该题满足二段性，可以用二分，二分的板子就不说了，接下来说一下check函数如何写。

第二阶段写check函数

check(mid)要实现的作用是当我知道了前mid个学生的成绩后，能否快速找出k名同学，使得他们的方差小于T。如果不能则返回false，否则返回true。我们希望选出来的k名同学的方差尽可能小，方差衡量的是数据之间的差值，自然要选择数据相近的k个值，所以我们可以对原始数据进行排序，然后选择连续的k个值就可以了。但是怎么快速计算选出来的k个值的方差呢？这就要根据方差公式了。

对于${\sum }_{i=1}^k{v}_i^2$、${\sum }_{i=1}^k{v}_i$，我们可以通过前缀和、前缀平方和或者滑动窗口的形式快速得到。而对于剩余的可以直接计算得出。所以代码如下，

static boolean check(int mid) {
        for (int i = 1; i <= mid; i++)
            b[i] = a[i];
        Arrays.sort(b, 1, mid + 1);//排序
        long v2 = 0, v = 0;
        for (int i = 1; i < k; i++) {//预处理数组b的前k-1项相关数据
            v2 += 1L * b[i] * b[i];//求平方和
            v += b[i];//求和
        }
        for (int i = k; i <= mid; i++) {
            v2 += 1L * b[i] * b[i] - 1L * b[i - k] * b[i - k];//类似滑动窗口，加上当前值，去掉已经滑出去的值
            v += b[i] - b[i - k];//类似滑动窗口，加上当前值，去掉已经滑出去的值
            double avg = 1.0 * v / k;//得到平均值
            if ((v2 - 2 * avg * v + k * avg * avg) / k < T)
                return true;
        }
        return false;
    }

刚刚的代码采用的是滑动窗口的思路，下面的代码使用的是前缀和的思路，

static boolean check(int mid) {
        for (int i = 1; i <= mid; i++)
            b[i] = a[i];
        Arrays.sort(b, 1, mid + 1);
        long[] sum_v2 = new long[mid+1], sum_v = new long[mid+1];
        for (int i = 1; i <= mid; i++) {
            sum_v2[i] = sum_v2[i-1] + 1L * b[i] * b[i];
            sum_v[i] =sum_v[i-1] + b[i];
        }
        for (int i = k; i <= mid; i++) {
            // v2 += 1L * b[i] * b[i] - 1L * b[i - k] * b[i - k];
            // v += b[i] - b[i - k];
            long v2 = sum_v2[i] - sum_v2[i-k];
            long v = sum_v[i] - sum_v[i-k];
            double avg = 1.0 * v / k;
            if ((v2 - 2 * avg * v + k * avg * avg) / k < T)
                return true;
        }
        return false;
    }

第三步二分范围确定

那么这里的高度的最小值是1，最大值就是数组中元素的个数，也就是n。注意本题没有说一定能找到符合条件的高度，所以最后输出的时候要判断一下。

题目代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, k, T;
    static int[] a, b;

    static boolean check(int mid) {
        for (int i = 1; i <= mid; i++)
            b[i] = a[i];
        Arrays.sort(b, 1, mid + 1);
        long[] sum_v2 = new long[mid+1], sum_v = new long[mid+1];
        for (int i = 1; i <= mid; i++) {
            sum_v2[i] = sum_v2[i-1] + 1L * b[i] * b[i];
            sum_v[i] =sum_v[i-1] + b[i];
        }
        for (int i = k; i <= mid; i++) {
            // v2 += 1L * b[i] * b[i] - 1L * b[i - k] * b[i - k];
            // v += b[i] - b[i - k];
            long v2 = sum_v2[i] - sum_v2[i-k];
            long v = sum_v[i] - sum_v[i-k];
            double avg = 1.0 * v / k;
            if ((v2 - 2 * avg * v + k * avg * avg) / k < T)
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        T = scanner.nextInt();
        a = new int[n + 1];
        b = new int[n + 1];
        for (int i = 1; i <= n; i++)
            a[i] = scanner.nextInt();
        int l = k, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if(check(l))System.out.println(l);
        else System.out.println(-1);
    }
}