二分+前缀和

REFERENCE

$由于是求方差，就需要理解方差的性质：反应的是数之间的差异程度\\ 方差越小，那么数之间的差越小\\ 那么让我选k个数使其方差最小的话\\ 我们首先将k个数排序，然后遍历求相邻k个数的方差，O(n)\\ 要求前x个数，就不能暴力枚举O(n) \rightarrow O(n^2)\\ 采用二分O(logn) $

$O(n)求方差最简单的办法：\rightarrow 将原式展开$
$$\sigma^2 = \dfrac{\sum\limits_{i=1}^{k}v_i^2 - \bar{v}\sum\limits_{i=1}^{k}2 * v_i+ k * \bar{v}^2}{k} $$
$利用前缀和求各个和$

/*
    满足二分性质，当x越大，越能找到这样的k
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long 

using namespace std;

const int N = 100010;

int a[N], bk[N], s[N], s2[N];
int n, k, T;

bool check(int x){
    memcpy(bk, a, sizeof a);
    sort(bk + 1, bk + x + 1);

    //前缀和求k个数的和
    for (int i = 1; i <= x; i ++){
        s[i] = s[i - 1] + bk[i];
        s2[i] = s2[i - 1] + bk[i] * bk[i];
    }

    for (int i = k; i <= x; i ++){
        int spowvi = s2[i] - s2[i - k], svi = s[i] - s[i - k];
        double avg = (double)svi / k;
        if ((double)spowvi - avg * 2 * svi + k * avg * avg < (double)k * T) return true;
    }

    return false;
}

signed main(){
    scanf("%lld%lld%lld", &n, &k, &T);

    for (int i = 1; i <= n; i ++) {
        scanf("%lld", &a[i]);
    }

    if (!check(n)){
        printf("%d\n", -1);
        return 0;
    }

    int l = 1, r = n;
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%lld\n", r);
    return 0;
}