蓝桥杯 2024 省赛 A：成绩统计

题目描述

有 $n$ 位同学，按照进教室的顺序依次得到编号 $1 \ldots n$ ，第 $i$ 位同学的成绩为 $a_i$ 。小蓝依次查看同学成绩：当他看完前 $x$ 位同学的成绩时，可以在这 $x$ 个人中任意挑出 $k$ 名同学，计算他们成绩的方差。请问至少需要查看多少位同学，才有可能找到一组方差严格小于阈值 $T$ 的 $k$ 人集合。如果始终无法满足条件，输出 $-1$ 。

方差 $\sigma^2$ 的定义为

\sigma^2 = \frac{1}{k}\sum_{i=1}^{k}(v_i-\bar v)^2,\quad \bar v = \frac{1}{k}\sum_{i=1}^{k}v_i.

输入格式

第一行：三个整数 $n,k,T$ 。
第二行： $n$ 个整数 $a_1,a_2,\ldots,a_n$ 。

输出格式

输出一个整数表示最少需要查看的同学数量；若无法找到满足条件的集合，输出 -1。

样例

前三人只能选到 $\{3,2,5\}$ ，方差为约 $1.56$ ；观察到第四人后可以选 $\{3,2,2\}$ ，方差约 $0.22 < 1$ ，因此答案为 4。

思路

对答案二分枚举 $x$ ，表示“只看前 $x$ 位同学”是否可行。
对前 $x$ 个成绩复制并排序，方差最小的 $k$ 人一定是排序后相邻的 $k$ 个。
使用前缀和维护滑动窗口内的和与平方和，快速计算每组 $k$ 个数的方差。
如果存在某组方差不超过阈值，则当前 $x$ 可行，继续收缩右端；否则扩大搜索范围。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long n, k, T;
long long a[MAXN], tmp[MAXN], prefix[MAXN], prefixSq[MAXN];

bool check(long long x) {
    for (int i = 1; i <= x; ++i) tmp[i] = a[i];
    sort(tmp + 1, tmp + x + 1);
    prefix[0] = prefixSq[0] = 0;
    for (int i = 1; i <= x; ++i) {
        prefix[i] = prefix[i - 1] + tmp[i];
        prefixSq[i] = prefixSq[i - 1] + tmp[i] * tmp[i];
    }
    auto variance = [&](int l, int r) {
        long long sum = prefix[r] - prefix[l - 1];
        long long sumSq = prefixSq[r] - prefixSq[l - 1];
        long double avg = (long double)sum / k;
        long double var = (sumSq - 2 * avg * sum + k * avg * avg) / k;
        return var;
    };
    for (int i = k; i <= x; ++i) {
        if (variance(i - k + 1, i) <= T) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> T;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    long long l = k, r = n, ans = -1;
    while (l <= r) {
        long long mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << '\n';
    return 0;
}