PAT-A 1012. The Best Rank (25)

2019-11-06 09:12:52

字体：大中小

来源：转载

供稿：网友

题目链接在此。

题意理解

已知N个学生的3门课程的分数C,M,E，平均分A可以通过三门课程求得。现在分别按这4个分数对考生进行从高到低的排序（对于每个考生而言就有4个顺序，每门课分数就会有一个排名）。

有M个查询，每个查询给出一个考生ID，需要输出该考生最高的那个排名的名次以及对应的科目。

如果不同的课程有相同的排名，则按照以下有衔接输出：A>C>M>E; 如果输入的考生号不存在，则输出N/A。

思路

定义一个结构体，这个结构体中包含考生号id，四门课分数以及四门课的排名需要一个以上结构体的数组用来保存输入更新结构体中的排名信息，则需要进行四次sort并且给出每个学生相应课程分数的排名获取查询，每获取一个遍历一遍结构体数组，存在查询的考生则输出相关信息，需要注意A>C>M>E的优先级

之前是想用结构体数组的下标来表示考生号ID，那样需要的空间超出了限制。《算法笔记》的思想则是“折中”了一下，它仅仅使用一个数组来保存每个学生每门课的排名：Rank[id][course]，第一维的id就可以避免一次次的遍历，而可以直接访问到查询的考生排名，并且四种成绩的对应字符也保存到了一个映射数组中，方便输出。

我的AC代码

#include<cstdio>#include<iostream>#include<algorithm>using namespace std;struct INFO{ int id; //对应科目 int C; int M; int E; int A; //对应科目的排名 int rc; int rm; int re; int ra;}stu[2005]; //stu下标就是student ID //为平均分排名bool cmp_A(INFO a, INFO b){ return a.A>b.A;} //为C语言排名bool cmp_C(INFO a, INFO b){ return a.C>b.C;}//为数学排名bool cmp_M(INFO a, INFO b){ return a.M>b.M;} //为英语排名bool cmp_E(INFO a, INFO b){ return a.E>b.E;}int main(){// init(); int N,M; scanf("%d %d",&N, &M); int id,temp[3]; //用来暂存输入的信息 (temp[0]:C, temp[1]:M, temp[2]:E) int sum; //记录三门总分 //input N students' info for(int i = 0; i < N; i++){ sum = 0; scanf("%d %d %d %d",&id,&temp[0],&temp[1],&temp[2]); //计算平均值 for(int j = 0; j < 3; j++){ sum += temp[j]; } int avg = sum/3; stu[i].id = id; stu[i].A = avg; stu[i].C = temp[0]; stu[i].M = temp[1]; stu[i].E = temp[2]; } //更新结构体中的排名信息 //更新ra（平均成绩排名） sort(stu,stu+N,cmp_A); stu[0].ra = 1; for(int i = 1; i < N; i++){ if(stu[i].A == stu[i-1].A){ stu[i].ra = stu[i-1].ra; }else{ stu[i].ra = i+1; } } //更新rc（平均成绩排名） sort(stu,stu+N,cmp_C); stu[0].rc = 1; for(int i = 1; i < N; i++){ if(stu[i].C == stu[i-1].C){ stu[i].rc = stu[i-1].rc; }else{ stu[i].rc = i+1; } } //更新rm（平均成绩排名） sort(stu,stu+N,cmp_M); stu[0].rm = 1; for(int i = 1; i < N; i++){ if(stu[i].M == stu[i-1].M){ stu[i].rm = stu[i-1].rm; }else{ stu[i].rm = i+1; } } //更新re（平均成绩排名） sort(stu,stu+N,cmp_E); stu[0].re = 1; for(int i = 1; i < N; i++){ if(stu[i].E == stu[i-1].E){ stu[i].re = stu[i-1].re; }else{ stu[i].re = i+1; } } while(M--){ scanf("%d",&id); int i; for(i = 0; i < N; i++){ if(id == stu[i].id){ int max = stu[i].ra; char sub = 'A'; //sunject 科目 if(stu[i].rc < max){ max = stu[i].rc; sub = 'C'; } if(stu[i].rm < max){ max = stu[i].rm; sub = 'M'; } if(stu[i].re < max){ max = stu[i].re; sub = 'E'; } PRintf("%d %c/n",max,sub); break; } } if(i>=N){ printf("N/A/n"); } } return 0;}

上一篇：bzoj1001 [BeiJing2006]狼抓兔子

下一篇：Tensorflow 框架下的NLP学习，收集学习资料中