小团是某综艺节目的策划,他为某个游戏环节设计了一种晋级规则,已知在这个游戏环节中每个人最后都会得到一个分数score_i,显而易见的是,游戏很有可能出现同分的情况,小团计划该环节晋级人数为x人,则将所有人的分数从高到低排序,所有分数大于等于第x个人的分数且得分不为0的人都可以晋级。 请你求出本环节的实际晋级人数。显然这个数字可能是0,如果所有人的得分都是0,则没有人满足晋级条件。
输入第一行包含两个正整数n和x,分别表示参加本环节的人数,和小团指定的x。 输入第二行包含n个整数,每个整数表示一位选手的得分。
输出仅包含一个整数,表示实际晋级人数。
5 4 0 0 2 3 4
3
考点:排序
限制 1 秒 / 256MB | 标准输入输出
推荐方向:排序
本题切入点
按分数降序排序,取第 x 名的分数作为门槛,统计所有分数不低于该门槛且不为 0 的人数。
先用 O(n log n) 排序把无序变有序,后续处理往往就简单了。
思路框架(排序 通法 · 非本题专属)
实现要点:在 C++ 中用 std::sort,Python 用 sorted();注意自定义比较函数的严格弱序。
复杂度:时间 O(n log n) | 空间 O(log n) ~ O(n)
该范式的通法易错点
样例 1
5 4 / 0 0 2 3 43解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:美团2023校招技术第9场编程题。