有一个比赛，晋级下一轮的规则是：“参赛者如果得分大于0且不小于排名第K的参赛者的得分，将晋级下一轮！” 现在已知有n名参赛者(n≥k)，以及他们各自的得分，现在你需要计算将有多少人晋级下一轮。 输入: 输入的第一行包含两个整数n和k(1≤k≤n≤50)，一空格分开。 第二行包含n个用空格分开的整数Ai(0≤Ai≤100)，表示排名第i的参赛者的得分。其中对任意的i满足Ai≥Ai+1。 输出: 输出将有多少人晋级下一轮。

算法1

（暴力枚举） $O(n^2)$

对于每一个参赛者，遍历排在他前面的k-1位参赛者，判断是否满足晋级规则即可。

时间复杂度

遍历n个参赛者，对于每个参赛者需要遍历k-1位参赛者，因此总时间复杂度为$O(n(k-1))=O(n^2)$。

C++ 代码

算法2

（排序） $O(n\log n)$

先将得分排序，然后从第k名开始遍历判断是否满足晋级规则。

时间复杂度

排序的时间复杂度为$O(n\log n)$，遍历的时间复杂度为$O(n-k)$，因此总时间复杂度为$O(n\log n)$。

C++ 代码

相关问题

有一个比赛，晋级下一轮的规则是参加者如果得分大于0且不小于排名k的参赛者得分，将晋级下一轮，先已知

所有参赛者的分数，请你确定哪些参赛者能够晋级。

具体地，假设当前参赛者的分数已经按从高到低排好序，分别为 scores = [score[0], score[1], ..., score[n-1]]，那么排名第 i 位参赛者的得分为 scores[i-1]，并且一定满足 scores[0] > scores[1] > ... > scores[n-1]。

示例：
输入：scores = [25, 21, 20, 13, 9, 8, 7, 6], k = 4
输出：[25, 21, 20, 13]
解释：根据规则，排名为 1、2、3 和 4 的参赛者可以晋级下一轮。

输入: 输入的第一行包含两个整数n和k(1≤k≤n≤50)，一空格分开。 第二行包含n个用空格分开的整数Ai(0≤Ai≤100)，表示排名第i的参赛者的得分。其中对任意的i满足Ai≥Ai+1。 输出: 输出将有多少人晋级下一轮。

算法思路：

首先将第K名参赛选手获取到的分数设为基准分，遍历每一个参赛选手，只要分数比基准分高且大于0，就可以晋级下一轮。

Python代码：

n, k = map(int, input().split())
scores = list(map(int, input().split()))

cut_off = scores[k-1] # 基准分数
count = 0 # 晋级人数
for score in scores:
if score >= cut_off and score > 0:
count += 1

print(count)