題目

1012 The Best Rank (25分)

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

理解與演算法

這道題理解起來不難，重點在怎么實作，

寫了三四天的PAT，慢慢有點感覺，能用簡單的資料結構就用簡單的資料結構，不要想著一個龐大的結構體包含你需要的所有狀態，這不現實，也不經濟，我們應該用足夠少的資料量，配合必須的資料容器，來表示全部的資訊，

我最開始的想法是用四個陣列來表示學生們的成績，而我們需要對資料進行排序，排序完會丟失學生資訊的完整性，就算你用四個結構體來系結學號和成績的資訊，還是會多很多的冗余資訊！

所以我們將學生的資訊打包成一個結構體，每次排序之后的排位資訊也存盤在這個結構體中，并記錄這個學生哪門課排名最好！

由上述資訊我們這么設計：

struct student {
    int id;
    int score[4];
    int rank[4];
    int best;
};

• id 學號，因為學號的長度有限制，所以我們可以直接用int型別來存盤，如果再大一點我們就用long int，這么做是為了方便快速存取
• score 成績資訊，為了對應不同科目的優先級，0-3分別為A，C，M，E，這樣也方便后面計算最佳排名
• rank 每門課的排位資訊，與上述成績score一一對應，
• best 最好的排名資訊，值為score與rank陣列的一個下標，

遇到的一個問題：

由于存在分數一樣的問題，所以如果直接用下標來表示學生成績的排名就會出現問題，因為一樣的分數就應該是一樣的排名，所以要和前一個學生進行比較，相同則繼承排名！

代碼與實作^[1]

//
// Created by tanknee on 2021/1/25.
//

#include <iostream>
#include <algorithm>

using namespace std;

struct student {
    int id;
    int score[4];
    int rank[4];
    int best;
};
student students[2001];

int exists[1000001], flag = -1;

bool cmp1(student a, student b) { return a.score[flag] > b.score[flag]; }

int main() {
    int N, M, id;
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        cin >> students[i].id >> students[i].score[1] >> students[i].score[2] >> students[i].score[3];
        students[i].score[0] = (students[i].score[1] + students[i].score[2] + students[i].score[3]) / 3.0 + 0.5;
    }
    // 計算學生每門課程的排名
    for (flag = 0; flag <= 3; flag++) {
        sort(students, students + N, cmp1);
        students[0].rank[flag] = 1;
        for (int i = 1; i < N; ++i) {
            students[i].rank[flag] = i + 1;
            // 如果分數相同，那么排名也跟之前的一樣
            if (students[i].score[flag] == students[i - 1].score[flag]) {
                students[i].rank[flag] = students[i - 1].rank[flag];
            }
        }
    }
    // 計算每個學生的最好排名
    for (int i = 0; i < N; ++i) {
        exists[students[i].id] = i + 1;
        students[i].best = 0;
        int min_num = students[i].rank[0];
        for (int j = 1; j <= 3; ++j) {
            if (students[i].rank[j] < min_num) {
                min_num = students[i].rank[j];
                students[i].best = j;
            }
        }
    }
    char tmp_chars[5] = {'A', 'C', 'M', 'E'};
    for (int i = 0; i < M; ++i) {
        cin >> id;
        int tmp = exists[id];
        if (tmp) {
            int best = students[tmp - 1].best;
            cout << students[tmp - 1].rank[best] << " " << tmp_chars[best] << endl;
        } else {
            cout << "N/A" << endl;
        }
    }
    return 0;
}

標籤：其他

上一篇：從URL輸入到頁面展現到底發生什么？

下一篇：2021寒假每日一題《滑雪場設計》