Skip to content

Latest commit

 

History

History
87 lines (76 loc) · 3.85 KB

1075. PAT Judge.md

File metadata and controls

87 lines (76 loc) · 3.85 KB

【PAT A-1075】PAT Judge

输入输出格式

输入第一行给出 3 个正整数 N、K、M，分别代表用户总数、题目综述、提交总数。之后一行给出 K 个正整数，分别代表每道题目的得分，题目由 1~K 编号。之后 M 行，每行按用户ID 题目编号 题目得分格式给出每个提交的信息，注意如果题目得分为-1，表示该题没有通过编译。

每行按排名 用户ID 总分 每一题的得分格式输出每个用户的信息。如果用户从未对某题进行过提交，则必须在相应位置打印-。 如果用户对某题进行过提交，则只统计最高分。输出时必须以排名降序打印；对于那些具有相同等级的用户，根据完全解决的问题的数量以飞增序对用户进行输出；如果仍然有相同的情况，则必须按身份证编号的升序打印。对于从未提交过任何可通过编译器的解决方案的人，或者从未提交过任何解决方案的人，不能将其打印出来。保证可以最后可以输出至少一个用户。

数据规模

$$N\le{10}^4,K\le 5,M\le{10}^5$$

算法设计

先定义学生类 Student，包含这些数据成员：学生 id、每题得分 score、解决题目个数 num、总分 total。每题得分默认都初始化为-2。定义一个unordered_map<string, Student>类型的变量 um，负责建立学生 ID 到 Student 对象之间的映射关系。读取每次提交时，将该提交得到的分数统计进 um 中，注意多次提交只统计最高分。然后将 um 中所有的值，也就是 Student 对象，迁移到vector<Student>类型的对象 stu 中。迁移的同时统计每个学生的总分以及解决题目的个数。然后按题目要求对 stu 进行排序。最后遍历 stu，按要求输出即可。具体实现可见代码。

注意点

具有相同成绩的学生应有相同的排名。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
struct Student {
    string id;
    array<gg, 5> score{-2, -2, -2, -2, -2};  //题目初始得分均为-2
    gg num = 0, total = 0;  //解决题目个数、总分
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    unordered_map<string, Student> um;
    gg ni, ki, mi;
    cin >> ni >> ki >> mi;
    vector<gg> problems(ki);
    for (gg& i : problems) {  //读取每题满分
        cin >> i;
    }
    while (mi--) {
        string id;
        gg pi, si;
        cin >> id >> pi >> si;
        um[id].score[pi - 1] =
            max(um[id].score[pi - 1], si);  //多次提交只统计最高分
    }
    vector<Student> stu;
    for (auto& i : um) {
        stu.push_back(i.second);
        auto& j = stu.back();
        j.id = i.first;  //存储用户ID
        for (gg t = 0; t < ki; ++t) {
            if (j.score[t] > 0) {  //总分中只累加得分大于0的题目
                j.total += j.score[t];
            }
            //如果该题拿到了满分，递增解决题目数
            if (j.score[t] == problems[t]) {
                ++j.num;
            }
        }
    }
    sort(stu.begin(), stu.end(), [](const Student& s1, const Student& s2) {
        return tie(s2.total, s2.num, s1.id) < tie(s1.total, s1.num, s2.id);
    });  //按要求排序
    gg r = 1;
    for (gg i = 0; i < stu.size(); ++i) {
        auto& s = stu[i];
        //如果没有任何通过编译的题目，不予输出
        if (all_of(s.score.begin(), s.score.end(),
                   [](gg a) { return a < 0; })) {
            continue;
        }
        if (i == 0 or s.total != stu[i - 1].total) {  //计算排名
            r = i + 1;
        }
        cout << r << " " << s.id << " " << s.total;
        for (gg k = 0; k < ki; ++k) {
            s.score[k] == -2 ? (cout << " -") :
                               (cout << " " << max(0ll, s.score[k]));
        }
        cout << "\n";
    }
    return 0;
}