PAT_ Class A_ 1025_PAT Ranking

General idea of the topic

There are N examination rooms, each with K candidates. Now give the admission number and score of candidates in each examination room. It is required to sort all candidates from high to low, and output the admission number, ranking, examination room number and ranking of all candidates in order.

Algorithm idea

This is a more conventional ranking question. The question requires to obtain the ranking of candidates in each examination room and the final ranking of all candidates together, so use it first
Vector < student > students [n + 1] to save the candidates in each examination room, and then use vector < student > stu to save the candidate set in all examination rooms. First, sort the students in examination room i directly by using the sort function to obtain the ranking, and then add the students who have obtained the ranking of the local examination room into the stu, and then sort the stu to obtain the final ranking of each candidate, and finally input according to the question requirements.

How to get ranking

For the first candidate after ranking, the ranking is 1, and then for other candidates, if the score is the same as that of the previous candidate, they will get the same ranking, otherwise it is equal to the number in the front plus 1.

Attention
  1. The candidate number is 13 digits and needs to be stored in character array or string.
  2. Here, the string type is used for storage. When inputting, the character array is used for input, and then the value is directly assigned to the string type variable. In this way, the use of high data volume is faster than that of cin input, and C must be used when inputting_ Convert the. Str () function to an array of characters
Submit results

Implementation code
#include<cstdio>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

int N;//Number of examination rooms
int K;//Number of people in each examination room

struct Student{
    string registration_number;// Candidate number, 13 digits
    int total_score; // Total score
    int location_number; // Examination room number, starting from 1
    int local_rank; // Ranking of this examination room
    int final_rank; // Final ranking
};

bool cmp(Student a,Student b){
    if (a.total_score!=b.total_score){
        return a.total_score>b.total_score;
    } else{
        return a.registration_number<b.registration_number;
    }
}

int main(){
    scanf("%d",&N);
    vector<Student> students[N+1]; // The collection of all candidates, studnets[i] is the collection of candidates whose examination room number is I
    vector<Student> stu; // Collection of all candidates
    int index = 0;
    char registration_number[15];
    for (int i = 1; i <=N; ++i) {
        scanf("%d",&K);
        for (int j = 0; j < K; ++j) {
            Student student;
            scanf("%s %d",registration_number,&student.total_score);
            student.registration_number = registration_number;
            student.location_number = i;
            students[i].push_back(student);
        }
    }
    // First, sort the students in this examination room to get the ranking
    for (int i = 1; i <= N; ++i) {
        sort(students[i].begin(),students[i].end(),cmp);
        // Calculate ranking
        for (int j = 0; j < students[i].size(); ++j) {
            if (j==0){
                students[i][j].local_rank = 1;// The first ranked 1
            } else if (students[i][j].total_score==students[i][j-1].total_score){
                // The total score is the same, and the ranking is the same
                students[i][j].local_rank = students[i][j-1].local_rank;
            } else{
                // The total score is different. The number of people in front of the ranking is plus one
                students[i][j].local_rank = j+1;
            }
            // After calculating the ranking of the examination room, join stu to obtain the final ranking
            stu.push_back(students[i][j]);
        }
    }
    // Rank all candidates
    sort(stu.begin(),stu.end(),cmp);
    // Get the total ranking of candidates
    for (int k = 0; k < stu.size(); ++k) {
        if (k==0){
            stu[k].final_rank = 1;
        } else if (stu[k].total_score==stu[k-1].total_score){
            stu[k].final_rank = stu[k-1].final_rank;
        } else{
            stu[k].final_rank = k+1;
        }
    }
    // Output the information of all candidates
    printf("%d\n",stu.size());
    for (int l = 0; l < stu.size(); ++l) {
        printf("%s %d %d %d\n",stu[l].registration_number.c_str(),stu[l].final_rank,stu[l].location_number,stu[l].local_rank);
    }
    return 0;
}

Tags: C++ Algorithm

Posted by zszucs on Mon, 16 May 2022 06:27:59 +0300