有 位同学，按照进教室的顺序依次得到编号 ，第 位同学的成绩为 。小蓝依次查看同学成绩：当他看完前 位同学的成绩时，可以在这 个人中任意挑出 名同学，计算他们成绩的方差。请问至少需要查看多少位同学，才有可能找到一组方差严格小于阈值 的 人集合。如果始终无法满足条件，输出 。
方差 的定义为
输出一个整数表示最少需要查看的同学数量；若无法找到满足条件的集合，输出 -1。
前三人只能选到 ，方差为约 ；观察到第四人后可以选 ，方差约 ，因此答案为 4。
输入
5 3 1
3 2 5 2 3
输出
4
#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;
}