PAT 1025 PAT Ranking (25分) vector + sort

题目

Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.

Input Specification: Each input file contains one test case. For each case, the first line contains a positive number N (≤100), the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer K (≤300), the number of testees, and then K lines containing the registration number (a 13-digit number) and the total score of each testee. All the numbers in a line are separated by a space.

Output Specification: For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:

registration_number final_rank location_number local_rank The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.

Sample Input: 2 5 1234567890001 95 1234567890005 100 1234567890003 95 1234567890002 77 1234567890004 85 4 1234567890013 65 1234567890011 25 1234567890014 100 1234567890012 85 Sample Output: 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

题目解读

1. 学生编号是 13 位数字，最后输出也一定要是13位，不足13位补前导0。
2. 假如 a b 分数相同，之后是 c d分数相同，排名是 1 1 3 3，而不是 1 1 2 2，也就是说，第二个人他把那个位置占了，但是排名要和他前面那个人保持一致。

思路分析

• 构建按结构体 `Student` 存储考试信息：因为编号是`13`位数字，所以不能用`int`，可以用 `long long` 或者 `char[]` 或者 `string`，但因为编号也要用于排序，字符串数组排序需要逐个比较字符，速度较慢，所以我们直接用 `long long` 存储了，直接比大小
• `vector<Student> total_stu` 保存全部学生信息，用 `vector<Student> local_stu` 保存考场内学生信息。
• 考场号按顺序编号 `1-N`，没读入一个考场的学生信息，就先按分数排名，得到考场内排名 `stu[i].local_rank`，注意分数相同排名相同，然后将其移入 total_stu。
• 多个考场考生信息全部统计完后，对 `total_stu` 进行排序，得到 每个考生的最终排名，同样需要调整分数相同排名相同。
• 最后，输出考生数目（`total_stu.size()`)，输出每个考生信息。

满分代码

```#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 考生信息
struct Student {
// 编号 13位数字
// string no; // 字符串排名需要逐个比较字符，速度慢，这里用空间换时间
long long no;
// 分数 最终排名 考场号 考场内排名
int score, final_rank, local_number, local_rank;
};

// 按分数降序
bool cmp(Student a, Student b) {
return a.score != b.score ? a.score > b.score : a.no < b.no;
}

int main() {

// N个考场，考场内M个考生
int n, m;
cin >> n;
// 保存全部考生信息
vector<Student> total_stu;
for (int i = 1; i <= n; ++i) {
// 当前考场 m 人
cin >> m;
// 保存当前考场考生信息
vector<Student> local_stu(m);
for (int j = 0; j < m; ++j) {
// 学号和分数
cin >> local_stu[j].no >> local_stu[j].score;
// 当前考场号
local_stu[j].local_number = i;
}
// 考场内按分数排名
sort(local_stu.begin(), local_stu.end(), cmp);
// 设置考场内排名，成绩相同排名应该一样，
// 再将当前考场内考生信息加入全部信息集合
local_stu[0].local_rank = 1;
total_stu.push_back(local_stu[0]);
for (int j = 1; j < m; ++j) {
// 并列
if (local_stu[j].score == local_stu[j - 1].score)
local_stu[j].local_rank = local_stu[j - 1].local_rank;
// 注意这里是 j + 1，不是 local_stu[j - 1].local_rank + 1
// 因为排名是 1 1 3 4 4 6 这样的规则
else
local_stu[j].local_rank = j + 1;
// 将他加入全部信息的集合
total_stu.push_back(local_stu[j]);
}
}
// 再对全部学生按成绩降序排名，得到考生的最终排名
sort(total_stu.begin(), total_stu.end(), cmp);
// 设置最终排名
total_stu[0].final_rank = 1;
for (int j = 1; j < total_stu.size(); ++j) {
// 并列
if (total_stu[j].score == total_stu[j - 1].score)
total_stu[j].final_rank = total_stu[j - 1].final_rank;
else
total_stu[j].final_rank = j + 1;
}

// 输出全部考生数目
cout << total_stu.size() << endl;
// 输出每个考生的 编号 总排名 考场号 考场内排名
// 注意编号要13位输出
for(int i = 0; i < total_stu.size(); i++)
printf("%013lld %d %d %d\n", total_stu[i].no, total_stu[i].final_rank, total_stu[i].local_number, total_stu[i].local_rank);

return 0;
}```

0 条评论

• PAT 1007 Maximum Subsequence Sum (25分) 最大连续子序列和

Given a sequence of K integers { N​1​​ , N​2​​ , ..., N​K​​ }. A continuous subs...

• PAT 1002 A+B for Polynomials (25分) 指数作为数组下标+系数作为值

This time, you are supposed to find A+B where A and B are two polynomials.

• PAT 1028 List Sorting (25分) 用char[]，不要用string

Excel can sort records according to any column. Now you are supposed to imitate ...

• 洛谷P2704 [NOI2001]炮兵阵地(状压dp)

司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示）...

• 如何利用栈实现表达式求值

可以直接得出计算结果：-7。对于人类来说，我们很容易计算出来，因为我们从左往右看，看到后面括号时，知道括号内的计算优先级最高，因此可以先计算括号内的，然后反过来...

• 学习 PixiJS — 补间动画

版权声明：本文为博主原创文章，欢迎转载，转载请注明出处。 https://blog.csdn...