成绩排序

题意

将成绩单按分数从高到低排列；同分时姓名字典序较小的学生在前。

思路

Python 的元组会从左到右比较。排序键写成 (-分数, 姓名)：负号把分数的升序改为降序，姓名仍按默认字典序升序比较。这样一条 sort 就表达了两级规则。

代码

Python代码

python

1
2
3
4
5
6
7student_count = int(input())
students = [input().split() for _ in range(student_count)]

# 元组 key 先比较负分数，再比较姓名，因此正好符合题目的两级规则。
students.sort(key=lambda student: (-int(student[1]), student[0]))
for name, score in students:
    print(name, score)

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#include <cstdio>

struct ren {
	char name[100];
	int c;
};
ren a[20];
int n;
int main(){
	scanf("%d",&n);
	int i,j;
	for(i = 1;i<=n;i++){
		scanf("%s",a[i].name);
		scanf("%d",&a[i].c);
	}
	for(i=1;i<=n-1;i++)
		for(j=1;j<=n-i;j++){
			if( a[j].c > a[j+1].c){
				ren t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
		}
	for(i=n;i>=1;i--){
		printf("%s %d\n",a[i].name,a[i].c);
	}
	return 0;
}

复杂度

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

总结

多关键字排序的关键是把每层规则依次写进元组键中。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结