成绩统计
问题描述
小蓝的班上有 n 个人，一次考试之后小蓝想统计同学们的成绩，第 i 名同学的成绩为 a[i]。当小蓝统计完前 x 名同学的成绩后，他可以从 1 ∼ x 中选出任意 k 名同学的成绩，计算出这 k 个成绩的方差。小蓝至少要检查多少个人的成绩，才有可能选出 k 名同学，他们的方差小于一个给定的值 T？
方差计算公式
k 个数 v1, v2, ..., vk 的方差 σ² 定义为：
σ² = (1 / k) * Σ(v[i] - v̄)² (i = 1, 2, ..., k)
其中，v̄ 表示 v 的平均值，计算公式为：
v̄ = (1 / k) * Σv[i] (i = 1, 2, ..., k)
输入格式
- 第一行包含三个正整数
n, k, T，相邻整数之间使用一个空格分隔。 - 第二行包含
n个正整数a1, a2, ..., an，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。如果不能满足条件，输出 -1。
样例输入
5 3 1
3 2 5 2 3
样例输出
4
样例说明
- 检查完前三名同学的成绩后，选出的成绩是
3, 2, 5，方差为 1.56。 - 检查完前四名同学的成绩后，选出的成绩是
3, 2, 2，方差为 0.33 < 1，符合要求，因此答案为4。
评测用例规模与约定
对于 10% 的评测用例，保证 1 ≤ n, k ≤ 10²；
对于 30% 的评测用例，保证 1 ≤ n, k ≤ 10³；
对于所有评测用例，保证 1 ≤ n, k ≤ 10⁵，1 ≤ T ≤ 2³¹ - 1。
c++代码
#include<bits/stdc++.h>using namespace std;long long n, k, T, g_left, g_right, x, ans, ex2, ex;
vector<long long> grades, middle, sum_ex, sum_ex2;int judge() {middle = vector<long long>(x + 1);sum_ex = vector<long long>(x + 1, 0);sum_ex2 = vector<long long>(x + 1, 0);for (int i = 0; i <= x; i++) {middle[i] = grades[i];}sort(middle.begin(), middle.end());sum_ex[0] = middle[0];sum_ex2[0] = middle[0] * middle[0];for (int i = 1; i <= x; i++) {sum_ex[i] = middle[i] + sum_ex[i - 1];sum_ex2[i] = middle[i] * middle[i] + sum_ex2[i - 1];}for (int i = k - 1; i <= x; i++) {if (i - k >= 0) ex2 = sum_ex2[i] - sum_ex2[i - k];else ex2 = sum_ex2[i];if (i - k >= 0) ex = sum_ex[i] - sum_ex[i - k];else ex = sum_ex[i];if (ex2 * k - (ex)*(ex) < T * k * k) return 1;}return 0;
}int main() {cin >> n >> k >> T;grades = vector<long long>(n);for (int i = 0; i < n; i++) {cin >> grades[i];}g_left = k - 1;g_right = n - 1;ans = -2;while (g_right >= g_left) {x = (g_left + g_right) / 2;if (judge() == 1) {g_right = x - 1;ans = x;}else g_left = x + 1;}cout << ans + 1<< endl;
}//by wqs
题目解析
你要找出最小的x需要二分查找策略，否则超时。
x确定之后就要给前x个数排序。
因为方差最小的k个数肯定是连续(从小到大排序)的k个数，我们要从所有连续的k个数里面判断方差是否小于T。
如果都大于等于T，说明前x个数不行。
只要有一个小于T，说明前x个数可以。
方差的计算用D(x) = e(x^2) - e(x)^2;
代码实现
二分策略查找x
g_left = k - 1;//左边界
g_right = n - 1;//右边界
ans = -2;
while (g_right >= g_left) {x = (g_left + g_right) / 2; //中间值if (judge() == 1) { //判断这个x是否可行g_right = x - 1;//可行更新右边界ans = x;}else g_left = x + 1;//不可行更新左边界
}
前x个数排序
因为方差最小的k个数肯定是连续(从小到大排序)的k个数，我们要从所有连续的k个数里面判断方差是否小于T。
middle = vector<long long>(x + 1);
for (int i = 0; i <= x; i++) {middle[i] = grades[i];
}
sort(middle.begin(), middle.end());
计算前x个所有连续k个数的方差
sum_ex sum_ex2简化运算
方差的计算用D(x) = e(x^2) - e(x)^2;
sum_ex存储前x个数的和, sum_ex2存储前x个数的平方和。
令ex2 = sum_ex2[i] - sum_ex2[i - k];
令ex = sum_ex[i] - sum_ex[i - k];
则e(x^2) = ex2 / k;
e(x) = ex / k;
这样我们计算e(x^2) 、e(x) 方便多了
sum_ex[0] = middle[0];
sum_ex2[0] = middle[0] * middle[0];
for (int i = 1; i <= x; i++) {sum_ex[i] = middle[i] + sum_ex[i - 1];sum_ex2[i] = middle[i] * middle[i] + sum_ex2[i - 1];
}
计算方差
令ex2 = sum_ex2[i] - sum_ex2[i - k];
令ex = sum_ex[i] - sum_ex[i - k];
则e(x^2) = ex2 / k;
e(x) = ex / k;
e(x^2) - e(x)^2 < T等价于
ex2 * k - ex*ex < T * k * k
这样我们就避免了使用除法，可以全部用整数了。
for (int i = k - 1; i <= x; i++) {if (i - k >= 0) ex2 = sum_ex2[i] - sum_ex2[i - k];else ex2 = sum_ex2[i];if (i - k >= 0) ex = sum_ex[i] - sum_ex[i - k];else ex = sum_ex[i];if (ex2 * k - (ex)*(ex) < T * k * k) return 1;
}
如果都大于等于T，说明前x个数不行。
只要有一个小于T，说明前x个数可以。
