奖学金

题意

每个学生有语文、数学、英语三科成绩。按总分降序、语文降序、学号升序的规则排列，输出前五名的学号和总分。

思路

读入时顺便计算总分，并保存 (学号, 语文, 总分)。排序键为 (-总分, -语文, 学号)：前两项取相反数得到降序，学号保持正数得到升序。排序结果前五项就是答案。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12student_count = int(input())
students = []

for student_id in range(1, student_count + 1):
    chinese, math, english = map(int, input().split())
    total = chinese + math + english
    students.append((student_id, chinese, total))

# 总分、语文分取相反数可得到降序；学号保持正数则为升序。
students.sort(key=lambda student: (-student[2], -student[1], student[0]))
for student_id, _, total in students[:5]:
    print(student_id, total)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/* 
 *   快速排序本质:
 *      用key值,把数据分成两个部分,一部分比较key小,一部分比key大
 * */

#include <cstdio>

int n;

struct _stu {
    int yw,sx,yy;
    int idx; //编号
};

_stu a[10010];

// 比较两个学生的大小 , 也就是哪个应该在前面
bool greater( _stu &a,_stu &b){
    int ta = a.yy+a.yw+a.sx;
    int tb = b.yy+b.yw+b.sx;
    if( ta > tb)
        return true;
    
    if( ta == tb  && a.yw > b.yw)
        return true;
    if(ta == tb && a.yw == b.yw && a.idx < b.idx)
        return true;
    if(a.idx == b.idx)
        return true;
    return false;
}

void xchg(_stu &a,_stu &b){
    _stu t = a;
    a = b;
    b =t;
}

void quicksort(int l,int r){

    if( l >= r) return;

    _stu key = a[l];
    int i = l, j = r;
    while( i != j){
        while(greater(key,a[j]) && i < j )
            j--;
        while(greater(a[i],key) && i < j)
            i++;
        if( i < j )
            xchg(a[i],a[j]);
    }

    a[l] = a[i];
    a[i] = key;

    quicksort(l,i-1);
    quicksort(i+1,r);
}

int main(){
	scanf("%d",&n);
	int i,j;
	//输入数据
	for(i=1;i<=n;i++){
	    a[i].idx = i;
	    scanf("%d%d%d", &a[i].yw, &a[i].sx, &a[i].yy);
	}
	quicksort(1,n);

    for(i=1;i<=5;i++)
        printf("%d %d\n",a[i].idx, a[i].yy+a[i].yw+a[i].sx);
    return 0;
}

复杂度

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

总结

多级排名不必手写比较函数，把各优先级按顺序放进排序键即可。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结