#T0090. 划线录取

0

划线录取

题目背景

学校组织了一次选拔考试,计划至少录取 mm 名考生。录取规则是:按成绩从高到低排序,取第 mm 名的成绩作为录取分数线,成绩达到分数线的考生全部录取(同分并列的考生也都录取)。因此实际录取人数可能多于 mm

题目描述

给定 nn 名考生的成绩(非负整数)和计划录取人数 mm

  1. 把成绩从高到低排列;
  2. 设第 mm 名的成绩为分数线 LL
  3. 统计成绩 L\ge L 的考生人数并输出。

输入格式

第一行两个整数 n,mn,m

第二行 nn 个非负整数,表示各考生成绩。

输出格式

一行一个整数,表示实际录取人数。

样例输入1

8 4
100 90 90 80 80 80 70 60

样例输出1

6

样例解释1

排序后为 100 90 90 80 80 80 70 60,第 44 名成绩为 8080,所有 80\ge 80 的考生共 66 人(80 分有 3 人并列,全部录取)。

样例输入2(稍大,含多处同分)

14 6
620 580 620 550 600 600 580 550 520 600 580 500 620 490

样例输出2

6

样例解释2

降序排列为 620 620 620 600 600 600 580 580 580 ...,第 66 名成绩为 600600,成绩 600\ge 600 的共 66 人;若 m=7m=7,分数线降到 580580,则会录取 99 人(580 分有 3 人并列)。

数据范围与约定

  • 1mn2000001\le m\le n\le 200\,000
  • 成绩为非负整数,0ai7000\le a_i\le 700
  • 当第 mm 名处存在同分时,所有同分考生都计入答案

提示

最直接的做法是把成绩降序排序,读出第 m1m-1 个位置的分数作为线,再数一遍不小于该线的人数;也可以利用成绩范围很小(07000\sim700)用计数统计完成。注意不要把"第 mm 名"理解成只录恰好 mm 个人。