本文主要是介绍PAT-ADVANCED1025——PAT Ranking，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED
原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805474338127872
题目描述：
题目翻译：
1025 PAT排名
编程能力测试（PAT）由浙江大学计算机科学与技术学院组织。 每个测试应该在几个地方同时运行，并且排名列表将在测试后立即合并。 现在，你的工作是编写一个程序来正确合并所有排名并生成最终排名。
输入格式：
每个输入文件包含一个测试用例。对每个测试用例，第一行包含一个正整数N(<= 100)，代表考场数量。接下来的N个考场信息，每个考场信息以一个正整数K(<= 300)开头，代表这个考场的考生总数，接下来的K行，每行包含一个13位的准考证号和该考生的分数。一行中的所有数字由一个空格分隔。
输出格式：
对每个测试用例，在第一行中打印出考生总数。然后以下述形式输出最终排名列表：
registration_number final_rank location_number local_rank考场编号从1到N。输出必须按照final_rank的非降序排列。拥有相同分数的考生有相同的排名且按registration_number的非降序排列。
输入样例：
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85输出样例：
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4知识点：排序
思路：先对每个考场的考生进行排序得到考生的考场排名，再对所有考生进行排序得到考生的总排名
用一个结构体student存储考生编号、成绩、考场号、最终排名、考场排名这5个信息。
时间复杂度是O(nlogn)，其中n为总考生数。空间复杂度是O(n)。
C++代码：
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>using namespace std;struct student {string number;int score;int final_rank;int location_number;int local_rank;
};int N;
vector<student> students[101];
vector<student> allStudents;bool cmp(student stu1, student stu2);int main() {scanf("%d", &N);int K;string number;int score;student stu;for(int i = 1; i <= N; i++) {scanf("%d", &K);for(int j = 0; j < K; j++) {cin >> number >> score;stu.number = number;stu.score = score;stu.location_number = i;students[i].push_back(stu);}}for(int i = 1; i <= N; i++) {sort(students[i].begin(), students[i].end(), cmp);}for(int i = 1; i <= N; i++) {for(int j = 0; j < students[i].size(); j++) {if(j > 0 && students[i][j].score == students[i][j - 1].score) {students[i][j].local_rank = students[i][j - 1].local_rank;} else {students[i][j].local_rank = j + 1;}allStudents.push_back(students[i][j]);}}sort(allStudents.begin(), allStudents.end(), cmp);for(int i = 0; i < allStudents.size(); i++) {if(i > 0 && allStudents[i].score == allStudents[i - 1].score) {allStudents[i].final_rank = allStudents[i - 1].final_rank;} else {allStudents[i].final_rank = i + 1;}}cout << allStudents.size() << endl;for(int i = 0; i < allStudents.size(); i++){cout << allStudents[i].number << " " << allStudents[i].final_rank << " " << allStudents[i].location_number << " " << allStudents[i].local_rank << endl;}
}bool cmp(student stu1, student stu2) {if(stu1.score == stu2.score) {return stu2.number.compare(stu1.number) > 0;} else {return stu1.score > stu2.score;}
}C++解题报告：
这篇关于PAT-ADVANCED1025——PAT Ranking的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
