蓝桥杯2024年第十五届省赛真题-成绩统计
目录
蓝桥杯2024年第十五届省赛真题-成绩统计
题目描述
小蓝的班上有 n 个人，一次考试之后小蓝想统计同学们的成绩，第 i 名同学的成绩为 ai 。当小蓝统计完前 x 名同学的成绩后，他可以从 1 ∼ x 中选出任意 k 名同学的成绩，计算出这 k 个成绩的方差。小蓝至少要检查多少个人的成绩，才有可能选出 k 名同学，他们的方差小于一个给定的值 T ？
提示：k 个数 v1, v2, · · · , vk 的方差 σ2 定义为：σ2 =∑ki=1(vi−v’)/k ，其中 v’ 表示v 的平均值，v’ =∑ki=1 vi/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 ≤ 102；
对于 30% 的评测用例，保证 1 ≤ n, k ≤ 103 ；
对于所有评测用例，保证 1 ≤ n, k ≤ 105 ，1 ≤ T ≤ 231 − 1 ，1 ≤ ai ≤ n 。
1.分析
我们需要找到 最小的x ，使得从1-x中选取k个数的方差小于k。
1.要想 方差小 ，就选取 最小的k个数 。
2.不提倡枚举2-n，用 二分 。
2.代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<cmath>
using namespace std;
typedef long long LL;
const int MAX = 1e5 + 100;
double h[MAX];
int n, k, T;
bool check(int d) { //检查前d个数是否满足
if (d < k) return false;
double a[MAX];
LL sum=0;
for (int i = 0; i < d; i++) { //获取前d个数
a[i] = h[i];
}
sort(a, a + d); //排序
for (int i = 0; i < k; i++) { //找到前k小的数
sum += a[i];
}
double v = sum*1.0 / k; //计算平均值
double re = 0;
for (int i = 0; i < k; i++) {
re += (a[i] - v) * (a[i] - v); //计算方差
}
if (re / k >= T) return false; //判断
return true;
}
int main() {
cin >> n >> k >> T;
for (int i = 0; i < n; i++) { //输入
cin >> h[i];
}
int l = 0, r = n-1; //二分
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (check(r)) cout << r << endl;
else cout << -1 << endl;
return 0;
}