题目描述
小蓝的班上有 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;
}
