Problem E: E: 成绩统计

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

小蓝的班上有 n 个人,一次考试之后小蓝想统计同学们的成绩,第 i 名同 学的成绩为 ai 。当小蓝统计完前 x 名同学的成绩后,他可以从 1 ∼ x 中选出任 意 k 名同学的成绩,计算出这 k 个成绩的方差。小蓝至少要检查多少个人的成 绩,才有可能选出 k 名同学,他们的方差小于一个给定的值 T ? 

提示:k 个数 v1, v2, · · · , vk 的方差 σ 2 定义为:σ 2 = ∑k i=1(vi−v_) k ,其中 v_ 表示 v 的平均值,v_ = ∑k i=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 ≤ 2 31 − 1 ,1 ≤ ai ≤ n 。