PAT甲级1012The Best Rank

Posted on | | Visitors:
Words count in article: 1,108 字 | Reading time ≈ 5 分

[toc]

题目介绍

  • 题目链接

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

  • 题目考点

    排序、模拟，重点在模拟而非排序

  • 题目难度

    PAT甲级25分

  • 题目大意

    给出多个学生的C语言（C）、数学（M）、英语成绩（E），要求四舍五入计算3门课的均分（A），请在这4个成绩中输出指定同学的best rank。

  • 输入

    • N：学生的数量，不超过2000
    • M：查询的数量，不超过2000
    • N个学生的成绩：每行包括学生ID（6个数字组成的string）、C语言成绩、数学成绩、英语成绩
    • M个要查询的学生ID

  • 输出

    • 对于要查询的每一个学生，在一行中输出其best rank以及此rank对应的科目
    • rank方法为A>C>M>E，如果有1个学生有多个best rank相同，则输出优先级高的那个
    • 如果查询的学生不存在，输出N/A。

题解

解题思路

  • 需要解决的问题

    • 如何求出best rank？

      要求best rank，就需要先求出每个学生每个科目的rank，然后取最优。

    • ID是6位数字，严格来讲需要用string保存，那如何定义索引进而通过索引获取学生信息？

    • 如何实现rank方法的优先级？

    • 如何判断学生是否存在？

  • 注意点

    • 淦，自己的思路卡在怎么处理ID了。大神的思路真的妙，我咋这么笨……

      思路：如果ID作为索引并不方便，用map或者数组将ID映射到索引是更好的方法。

    • 关于best rank，我开始想的是进行多次排序，每次排序后更新best rank。

      如果这么做，因为rank有优先级就需要按照A、C、M、E的顺序排序，这样也是可行的。

      但我没想到用数组保存多个分数，这样可以通过index来循环，就不用重复写几次排序和rank更新，同时可以在存储/遍历的时候就按照ACME的顺序存储/遍历以简化程序逻辑。这里的关键点是用数组和循环的方式实现一个操作的多次重复。

    • 排名不能是1,1,2,3,4，应该是1,1,3,4,5。

代码

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
72
73
// Problem: PAT Advanced 1012
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805502658068480
// Tags: 排序

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

int s; // 课程（Subject）的索引，[0,3]，studentCmp需要使用

struct Student{
    string id;
    int score[4]; // A C M E
    int rank[4];
    int bestSubject;
} students[2000];

bool studentCmp(Student& a, Student & b){
    return a.score[s] > b.score[s]; // 从大到小排序
}

int main()
{
    // 读取数据
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        cin >> students[i].id;
        scanf("%d %d %d", &students[i].score[1], &students[i].score[2], &students[i].score[3]);
        students[i].score[0] = (students[i].score[1] + students[i].score[2] + students[i].score[3])/3.0 + 0.5;
    }

    // 计算每个学生4个成绩的rank
    for (s=0; s < 4; s++){
        // 按不同科目的成绩排序，s用以选择科目
        sort(students, students+n, studentCmp);
        students[0].rank[s] = 1;
        for (int i=1; i<n;i++){
            if (students[i].score[s] == students[i-1].score[s]) // 同分则rank相同
                students[i].rank[s] = students[i-1].rank[s];
            else
                students[i].rank[s] = i+1;
        }
    }
    // 计算每个学生的best rank
    map<string, int> mm; // 至此，学生数组students中学生的索引不再变化，将学生ID映射到索引
    for (int i=0; i<n; i++){ // 遍历学生
        mm[students[i].id] = i + 1; // map中索引是int，默认值为0，所以索引需要+1避免和0混淆

        students[i].bestSubject = 0; // 计算该学生的best rank（记录best rank对应科目的索引）
        for (int j=1; j<4; j++){
            if (students[i].rank[j] < students[i].rank[students[i].bestSubject])
                students[i].bestSubject = j;
        }
    }

    // 输出查询结果
    char symbol[] = {'A', 'C', 'M', 'E'};
    string studentID;
    for(int i=0, index, bestSubject; i<m; i++){
        cin >> studentID;
        if (mm[studentID] != 0){
            index = mm[studentID] - 1;
            bestSubject = students[index].bestSubject;
            printf("%d %c\n", students[index].rank[bestSubject], symbol[bestSubject]);
        }
        else
            printf("N/A\n");
    }
    return 0;
}

参考链接

Github（github.com）：@chouxianyu

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

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

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

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

微信公众号：@臭咸鱼

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