专栏首页vblogPAT 1025 PAT Ranking (25分) vector + sort

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

题目解读

这题看的我真费劲,英语硬伤啊,不过看懂题目之后发现这题一点都不难啊,大概意思是说:给出n个考场,给出每个考场内的考生数目m、考生的编号、分数,让最终输出考生的最终排名,输出格式是:==编号 总排名 考场号 考场内排名==,要求排名是按照分数从高到底到底,如果分数一样就并列,但是要学号小的在前。

注意点:

  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()),输出每个考生信息。

满分代码

注意输出编号一定要是 printf("%013lld", stu[i].no),不然你最后一个用例过不了。

#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...

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

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

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

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

    vivi
  • 创建带httpd服务的CentOS Docker镜像

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

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

    attack
  • PyQt的一个UI单元测试框架思路

    專 欄 ❈丁果,Python中文社区作者。对django、pyqt、opencv、tornado感兴趣。 GitHub:https://github.com/...

    Python中文社区
  • Sklearn参数详解—LR模型

    张俊红
  • 五步让表格变身特色PPT目录

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

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

    编程珠玑
  • 学习 PixiJS — 补间动画

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

    FEWY

扫码关注云+社区

领取腾讯云代金券