题目描述
有 位同学，按照进教室的顺序依次得到编号 ，第 位同学的成绩为 。小蓝依次查看同学成绩：当他看完前 位同学的成绩时，可以在这 个人中任意挑出 名同学，计算他们成绩的方差。请问至少需要查看多少位同学，才有可能找到一组方差严格小于阈值 的 人集合。如果始终无法满足条件，输出 。
方差 的定义为
输入格式
输出格式
输出一个整数表示最少需要查看的同学数量；若无法找到满足条件的集合，输出 -1。
样例
1
2
3
4
5
6
| 输入
5 3 1
3 2 5 2 3
输出
4
|
前三人只能选到 ，方差为约 ；观察到第四人后可以选 ，方差约 ，因此答案为 4。
思路
- 对答案二分枚举 ，表示“只看前 位同学”是否可行。
- 对前 个成绩复制并排序，方差最小的 人一定是排序后相邻的 个。
- 使用前缀和维护滑动窗口内的和与平方和，快速计算每组 个数的方差。
- 如果存在某组方差不超过阈值，则当前 可行，继续收缩右端；否则扩大搜索范围。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #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;
}
|
