一、题目描述

To evaluate the performance of our first year CS majored students, we consider their grades of three courses only: C - C Programming Language, M - Mathematics (Calculus or Linear Algrbra), and E - English. At the mean time, we encourage students by emphasizing on their best ranks – that is, among the four ranks with respect to the three courses and the average grade, we print the best rank for each student.

For example, The grades of C, M, E and A - Average of 4 students are given as the following:

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

Then the best ranks for all the students are No.1 since the 1st one has done the best in C Programming Language, while the 2nd one in Mathematics, the 3rd one in English, and the last one in average.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 numbers N and M (≤2000), which are the total number of students, and the number of students who would check their ranks, respectively. Then N lines follow, each contains a student ID which is a string of 6 digits, followed by the three integer grades (in the range of [0, 100]) of that student in the order of C, M and E. Then there are M lines, each containing a student ID.

​​Output Specification:

For each of the M students, print in one line the best rank for him/her, and the symbol of the corresponding rank, separated by a space.

The priorities of the ranking methods are ordered as A > C > M > E. Hence if there are two or more ways for a student to obtain the same best rank, output the one with the highest priority.

If a student is not on the grading list, simply output N/A.

Sample Input:

5 6 310101 98 85 88 310102 70 95 88 310103 82 87 94 310104 91 91 91 310105 85 90 90 310101 310102 310103 310104 310105 999999

Sample Output:

1 C 1 M 1 E 1 A 3 A N/A

二、解题思路

这道题的基本思想不难，但是比较复杂。输入学生数量N以及要查询的数量M，随后N行输入每个同学的学号以及三科成绩，后M行输入待查询的学生编号，要求输出排名最高是多少以及对应的科目，若不存在该学生，则输出N/A。我对这道题的想法呢，就是把学生设置成一个结构体，包括id和一个成绩数组，我们按题目给的优先级来编号，即0-A，1-C，2-M，3-E。用一个vector<Student>来存放输入的这些信息。输入完之后，计算平均成绩，即grade[0]，注意这里按题目样例来看的话，是应该有一个四舍五入，我们可以用round函数，但是经过实测发现，其实不四舍五入也能AC。接下来，我们要利用全局变量now，表示现在在进行比较的成绩是哪一个，now从0到3，编一个循环，每一次对vector排一次序，将对应的排名存放在一个二维数组 ranking[1000000][4]中，这里实际上是以空间换时间了，学生编号即数组第一个下标，对应科目即第二个下标，数组中的值即为排名。通过循环某个学生的所有排名，即可得出排名最高的是什么科目。

三、AC代码

#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cmath> using namespace std; struct Student { int id, grade[4]; }; vector<Student> stu; int now; int ranking[1000000][4]; bool cmp(Student a, Student b) {return a.grade[now] > b.grade[now];} char course[4] = {'A', 'C', 'M', 'E'}; int main() { Student tmp; int N, M, temp; scanf("%d%d", &N, &M); for(int i=0; i<N; i++) { scanf("%d%d%d%d", &tmp.id, &tmp.grade[1], &tmp.grade[2], &tmp.grade[3]); tmp.grade[0] = round((tmp.grade[1] + tmp.grade[2] + tmp.grade[3])/3.0); stu.push_back(tmp); } for(now=0; now<4; now++) { sort(stu.begin(), stu.end(), cmp); for(int i=0; i<N; i++) { if(i==0) ranking[stu[i].id][now] = 1; if(stu[i].grade[now] == stu[i-1].grade[now]) ranking[stu[i].id][now] = ranking[stu[i-1].id][now]; else ranking[stu[i].id][now] = i+1; } } for(int i=0; i<M; i++) { scanf("%d", &temp); if(ranking[temp][0] == 0) printf("N/A\n"); else { int mk = 0; for(int j=0; j<4; j++) { if(ranking[temp][j] < ranking[temp][mk]) mk = j; } printf("%d %c\n", ranking[temp][mk], course[mk]); } } return 0; }