PAT-ADVANCED1012——The Best Rank
我的PAT-ADVANCED代码仓:https://github.com/617076674/PAT-ADVANCED
原题链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805502658068480
题目描述:
题目翻译:
1012 最好的排名
为了评估我们第一年CS专业学生的表现,我们只考虑他们三门课程的成绩:C - C程序设计语言,M - 数学(微积分或线性代数)和E - 英语。 与此同时,我们鼓励学生强调他们的最佳排名 - 即在三门课程和平均成绩的四个等级中,我们为每个学生打印最佳排名。
例如,C,M,E和A的成绩 - 平均4名学生如下:
StudentID C M E A
310101 98 85 88 90
310102 70 95 88 84
310103 82 87 94 88
310104 91 91 91 91
所有学生的最佳排名都是No.1,因为第一个学生在C语言编程方面做得最好,而第二个在数学方面,第三个在英语,最后一个平均。
输入格式:
每个输入文件包含一个测试用例。 每个测试用例都以包含2个数字N和M(≤2000)的行开头,这两个数字分别是学生总数和查询他们的等级的学生人数。 然后是N行,每行包含一个6位数字的学生ID,然后是该学生的三个整数等级(在[0,100]范围内),顺序为C,M和E。接下来的M行,每行包含一个学生ID。
输出格式:
对于每个M学生,在一行中打印出他/她的最佳等级,以及相应等级的符号,用空格分隔。
排名方法的优先级按A> C> M> E排序。因此,如果学生有两种或更多种方式获得相同的最佳排名,则输出具有最高优先级的方法。
如果学生不在评分列表中,只需输出N / A。
知识点:排序
思路:用一个结构体student里的数组grade来保存4种成绩减少代码书写量
本题不难,关键是如何定义好的结构体,来减少我们代码的书写量。
考虑到优先级为A > C > M > E,不妨在设置数组时就按这个顺序分配序号为0 ~ 3的元素,即0对应A、1对应C、2对应M及3对应E。
以结构体student存放6位整数ID和4个分数(grade[0] ~ grade[3]分别代表A、C、M、E)。
由于ID是6位整数,因此不妨设置Rank[1000000][4]数组,其中Rank[id][0] ~ Rank[id][3]表示编号为id的考生的4个分数各自在所有考生中的排名。
要注意优先级顺序是A > C > M > E,所以为了方便枚举,在设置char course[4]数组时也按这个顺序来设置。
时间复杂度是O(NlogN)。空间复杂度是O(N)。
C++代码:
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
struct student {
int id; //存放6位整数的ID
int grade[4]; //存放4个分数
};
int N, M;
student stu[2010];
char course[4] = {'A', 'C', 'M', 'E'}; //按优先级顺序,方便输出
int Rank[1000000][4] = {0}; //Rank[id][0] ~ Rank[id][4]为4门课对应的排名
int now; //cmp函数中使用,表示当前按now号分数排序stu数组
bool cmp(student a, student b); //stu数组按now号分数递减排序
int main(){
cin >> N >> M;
for(int i = 0; i < N; i++){
cin >> stu[i].id >> stu[i].grade[1] >> stu[i].grade[2] >> stu[i].grade[3];
stu[i].grade[0] = (stu[i].grade[1] + stu[i].grade[2] + stu[i].grade[3]) / 3;
}
for(now = 0; now < 4; now++){
sort(stu, stu + N, cmp);
Rank[stu[0].id][now] = 1;
for(int i = 1; i < N; i++){
if(stu[i].grade[now] == stu[i - 1].grade[now]){
Rank[stu[i].id][now] = Rank[stu[i - 1].id][now];
}else{
Rank[stu[i].id][now] = i + 1;
}
}
}
int query;
for(int i = 0; i < M; i++){
cin >> query;
if(Rank[query][0] == 0){
cout << "N/A" << endl;
}else{
int k = 0;
for(int j = 1; j < 4; j++){
if(Rank[query][j] < Rank[query][k]){
k = j;
}
}
cout << Rank[query][k] << " " << course[k] << endl;
}
}
return 0;
}
bool cmp(student a, student b) {
return a.grade[now] > b.grade[now];
}
C++解题报告: