【PAT-Advanced】1012 The Best Rank

发表于 | 分类于 ， | | 阅读次数:

Problem

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


Solution

题目不太难，比较考察对STL的应用

题目对算法复杂度要求不太高，所以直接用STL的sort函数排序，线性遍历

用到vector以及一些相关的函数

思路是，用vector存储学生的列表和分数的列表，将分数列表中的分数按从大到小排序之后，下标即对应排名（其中如果有相同分数，取最小的下标）

需要注意的是：

  • 相同分数的排序
    如95 90 90 88排名是1 2 2 4
  • 优先级A > C > M > E
  • 平均分取整（直接int就行）

代码如下

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
using namespace std;

//0 1 2 3
//A C M E

struct student{
    int id;
    int grade[4]; //各科分数
    int rank[4]; //各科排名
    int bestRank; //最高排名，0表示还没找
    int bestCourse; //最高排名对应的学科
};

vector<struct student> students; //学生列表
vector<int> Rank[4]; //分数列表，下标对应排名

char course[4] = {'A', 'C', 'M', 'E'};
int M, N;

bool cmp(int a, int b){
    return a > b;
}

//找到该学生各科分数对应的排名
struct student findRank(struct student stu){
    int ra, rc, rm, re;
    for(int i=0; i<4; i++){
        for(int j=0; j<Rank[i].size(); j++){
            if(Rank[i][j] == stu.grade[i]){
                stu.rank[i] = j + 1;
                break; //注意这个break不能漏
            }
        }
    }
    //找最高排名，标注对应课程
    ra = stu.rank[0];
    rc = stu.rank[1];
    rm = stu.rank[2];
    re = stu.rank[3];
    if(ra <= rc){
        if(ra <= rm){
            if(ra <= re){
                stu.bestRank = ra;
                stu.bestCourse = 0;
            }else{
                stu.bestRank = re;
                stu.bestCourse = 3;
            }
        }else{
            if(rm <= re){
                stu.bestRank = rm;
                stu.bestCourse = 2;
            }else{
                stu.bestRank = re;
                stu.bestCourse = 3;
            }
        }
    }else{
        if(rc <= rm){
            if(rc <= re){
                stu.bestRank = rc;
                stu.bestCourse = 1;
            }else{
                stu.bestRank = re;
                stu.bestCourse = 3;
            }
        }else{
            if(rm <= re){
                stu.bestRank = rm;
                stu.bestCourse = 2;
            }else{
                stu.bestRank = re;
                stu.bestCourse = 3;
            }
        }
    }
    return stu;
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    int id, c, m, e, a;
    struct student newStu;
    for(int i=0; i<N; i++){
        cin >> id >> c >> m >> e;
        a = (c + m + e) / 3; //平均分
        newStu.id = id;
        newStu.grade[0] = a;
        Rank[0].push_back(a);
        newStu.grade[1] = c;
        Rank[1].push_back(c);
        newStu.grade[2] = m;
        Rank[2].push_back(m);
        newStu.grade[3] = e;
        Rank[3].push_back(e);
        students.push_back(newStu);
    }
    //各分数列表按从高到低排序
    for(int i=0; i<4; i++){
        sort(Rank[i].begin(), Rank[i].end(), cmp);
    }
    for(int i=0; i<M; i++){
        cin >> id;
        int find = 0;
        for(int j=0; j<N; j++){
            if(students[j].id == id){
                find = 1;
                //如果已经找到过最佳排名就不用再调一遍函数，直接输出就好。否则调函数求一下
                //（减少重复检索时候的复杂度）
                if(students[j].bestRank == 0){ 
                    students[j] = findRank(students[j]);
                }
                cout << students[j].bestRank << " " << course[students[j].bestCourse] << endl;
            }
        }
        if(find == 0){
            cout << "N/A" << endl;
        }
    }
    return 0;
}