蓝桥杯2024年第十五届省赛真题-成绩统计

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

提示：k 个数 v1, v2, · · · , vk 的方差 σ2 定义为：σ2 =∑^k_i=1(v_i−v')/k ，其中 v' 表示v 的平均值，v' =∑^k_i=1 v_i/k 。

输入的第一行包含三个正整数 n, k, T ，相邻整数之间使用一个空格分隔。

第二行包含 n 个正整数 a₁, a₂, · · · , a_n ，相邻整数之间使用一个空格分隔。

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^{31 − 1} ，1 ≤ a_i ≤ n 。