谁考了第k名

题意

给出每位学生互不相同的成绩，输出成绩第 $k$ 高的学号和分数。题目要求分数按 %g 的效果输出，不能固定小数位。

思路

把每位学生记成 (学号, 成绩)，按成绩降序排列。Python 列表下标从 0 开始，因此第 $k$ 名位于 rank - 1。

f"{score:g}" 与 C/C++ 的 %g 类似，会去掉不必要的小数末尾零。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10student_count, rank = map(int, input().split())
students = []

for _ in range(student_count):
    student_id, score = input().split()
    students.append((student_id, float(score)))

# 成绩互不相同，按成绩从高到低排列后第 rank 个即为答案。
student_id, score = sorted(students, key=lambda student: student[1], reverse=True)[rank - 1]
print(student_id, f"{score:g}")

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <cstdio>

char str[105][105];
int xh[105];
double fs[105];
int n,k;
int main(){
	int i,j;
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++){
		scanf("%s",str[i]);
		xh[i] = i;
		scanf("%lf",&fs[i]);
	}
	for(i=1;i<=n-1;i++)
		for(j=1;j<=n-i;j++){
			if( fs[j] > fs[j+1]){
				double t = fs[j];
				fs[j] = fs[j+1];
				fs[j+1] = t;
				
				int x = xh[j];
				xh[j] = xh[j+1];
				xh[j+1] = x; 
			} 
		}
	int p = n-k+1;
	printf("%s %g",str[xh[p]],fs[p]); 
	
	return 0;
}

复杂度

排序时间复杂度为 $O(n \log n)$ ，额外空间复杂度为 $O(n)$ 。

总结

排序后直接按排名取元素。需要注意的是，名次从 1 开始而列表下标从 0 开始。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结