PAT甲级1025PAT Ranking

Posted on | | Visitors:
Words count in article: 731 字 | Reading time ≈ 3 分

[toc]

题目介绍

  • 题目链接

    https://pintia.cn/problem-sets/994805342720868352/problems/994805474338127872

  • 题目考点

    排序、模拟。排序是简单的结构体排序，模拟也不难。这题比较简单（我竟然没看题解做出来了，捂脸）

  • 题目难度

    PAT甲级25分

  • 题目大意

    汇总PAT各个考场的ranklist，生成最后的rank

  • 输入

    • N：正数，不超过100，考场的数量

    • N个ranklist：

      1个ranklist包括：第1个数字是K（正整数，不超过300，考生数量），然后K行，每行包括注册号（13位数字）和考生总分

  • 输出

    • 考生总数

    • 最终的ranklist：包括注册号、final rank、考场号（索引为[1,N]）、考场中排名

      先按final rank非降序输出，再按注册号非降序输出。

题解

解题思路

  • 每读取1个考场的考生数据，就将其存入该考场的vector，然后排序计算local rank，再存入保存所有考生的vector，最后把所有考生排序，计算final rank，输出。

  • 要根据分数排序，输出时还要根据排名和注册号排序

    后者已经包括了前者，因为rank升序就是分数降序，所以写一个排序函数就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Problem: PAT Advanced 1025
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805474338127872
// Tags: 排序 模拟

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Testee{
    string id;
    int location, score, rank[2];

    Testee(){}
    Testee(string id_, int location_, int score_){
        id = id_;
        location = location_;
        score = score_;
    }

    void display(){
        cout << id;
        printf(" %d %d %d\n", rank[1], location, rank[0]);
    }
};

bool testeeCmp(Testee& a, Testee& b){
    return a.score==b.score ? a.id<b.id : a.score>b.score ;
}

void calcRank(vector<Testee>& testees,int j){
    testees[0].rank[j] = 1;
    for (int i=1; i < testees.size(); i++){
        if (testees[i].score == testees[i-1].score)
            testees[i].rank[j] = testees[i-1].rank[j];
        else
            testees[i].rank[j] = i+1;
    }
}

int main()
{
    // 定义变量
    int n, k, score;
    string id;
    scanf("%d", &n);
    vector<Testee> allTestees;
    // 读取输入，并计算local rank，将不同考场的考生保存到同1个vector里
    for (int i=1; i<=n; i++){ // 遍历考场
        scanf("%d", &k);
        vector<Testee> localTestees(k);
        for (int j=0; j<k; j++){ // 读取考生信息
            cin >> localTestees[j].id >> localTestees[j].score;
            localTestees[j].location = i;
        }
        sort(localTestees.begin(), localTestees.end(), testeeCmp);
        calcRank(localTestees, 0); // 计算该考场考生的local rank
        for (int j=0; j<k; j++) // 将不同考场的考生保存到一个vector里
            allTestees.push_back(localTestees[j]);
    }
    // 计算final rank
    sort(allTestees.begin(), allTestees.end(), testeeCmp);
    calcRank(allTestees, 1);
    // 输出结果
    printf("%d\n", allTestees.size());
    for (int i=0; i < allTestees.size(); i++){
        allTestees[i].display();
    }
    return 0;
}

Github（github.com）：@chouxianyu

Github Pages（github.io）：@臭咸鱼

知乎（zhihu.com）：@臭咸鱼

博客园（cnblogs.com）：@臭咸鱼

B站（bilibili.com）：@绝版臭咸鱼

微信公众号：@臭咸鱼

转载请注明出处，欢迎讨论和交流!