[蓝桥杯 2024 省 A] 成绩统计

Luogu
IDLGP10389
Time1000ms
Memory512MB
DifficultyP4
数学二分2024蓝桥杯省赛
小蓝的班上有 $n$ 个人,一次考试之后小蓝想统计同学们的成绩,第 $i$ 名同学的成绩为 $a_i$。当小蓝统计完前 $x$ 名同学的成绩后,他可以从 $1 \sim x$ 中选出任意 $k$ 名同学的成绩,计算出这 $k$ 个成绩的方差。小蓝至少要检查多少个人的成 绩,才有可能选出 $k$ 名同学,他们的方差小于一个给定的值 $T$? 提示:$k$ 个数 $v_1, v_2, \cdots , v_k$ 的方差 $\sigma^2$ 定义为:$\sigma^2=\dfrac {\sum_{i=1}^k(v_i-\bar v)^2} k$,其中 $\bar v$ 表示 $v_i$ 的平均值,$\bar v = \dfrac {\sum_{i=1}^k v_i} k$。 ## Input 输入的第一行包含三个正整数 $n, k, T $,相邻整数之间使用一个空格分隔。 第二行包含 $n$ 个正整数 $a_1, a2, \cdots, a_n$ ,相邻整数之间使用一个空格分隔。 ## Output 输出一行包含一个整数表示答案。如果不能满足条件,输出 $-1$ 。 [samples] ## Note 检查完前三名同学的成绩后,只能选出 $3, 2, 5 $,方差为 $1.56 $; 检查完前四名同学的成绩后,可以选出 $3, 2, 2 $,方差为 $0.22 < 1 $,所以答案为 $4 $。 对于 $10\%$ 的评测用例,保证 $1 ≤ n, k ≤ 10^2$; 对于 $30\%$ 的评测用例,保证 $1 ≤ n, k ≤ 10^3$ ; 对于所有评测用例,保证 $1 ≤ n, k ≤ 10^5 $,$1 ≤ T ≤ 2 ^{31} -1 $,$1 ≤ a_i ≤ n $。
Samples
Input #1
5 3 1
3 2 5 2 3
Output #1
4
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2024 省 A] 成绩统计",
    "description": {
      "content": "小蓝的班上有 $n$ 个人,一次考试之后小蓝想统计同学们的成绩,第 $i$ 名同学的成绩为 $a_i$。当小蓝统计完前 $x$ 名同学的成绩后,他可以从 $1 \\sim x$ 中选出任意 $k$ 名同学的成绩,计算出这 $k$ 个成绩的方差。小蓝至少要检查多少个人的成 绩,才有可能选出 $k$ 名同学,他们的方差小于一个给定的值 $T$? 提示:$k$ 个数 $v_1, v_2, \\cdots ,",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10389"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小蓝的班上有 $n$ 个人,一次考试之后小蓝想统计同学们的成绩,第 $i$ 名同学的成绩为 $a_i$。当小蓝统计完前 $x$ 名同学的成绩后,他可以从 $1 \\sim x$ 中选出任意 $k$ 名同学的成绩,计算出这 $k$ 个成绩的方差。小蓝至少要检查多少个人的成\n绩,才有可能选出 $k$ 名同学,他们的方差小于一个给定的值 $T$?\n提示:$k$ 个数 $v_1, v_2, \\cdots ,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments