Skip to content

Latest commit

 

History

History
48 lines (39 loc) · 1.68 KB

1039. Course List for Student.md

File metadata and controls

48 lines (39 loc) · 1.68 KB

【PAT A-1039】Course List for Student

输入输出格式

输入第一行给出两个正整数 N 和 K,分别表示要查询的学生个数和课程数。课程从 1~K 编号。接下来 K 组输入,每组第一行给出两个正整数 i 和$N_i$,分别表示课程编号以及选了该课的学生个数。第二行给出$N_i$个学生的 ID。输入的最后一行给出 N 个要查询的学生 ID,要求查询这 N 个学生选的所有课程编号。

对应查询的每个学生输出一行,先输出这个学生的 ID,然后输出这个学生选择的课程数量,最后按升序输出这个学生选择的所有课程编号。

数据规模

$$N\le {10}^4,K\le 2500$$

算法设计

需要建立一种映射关系:学生 ID 到该学生选择的全部课程,这种映射可以用unordered_map<string, set<gg>>表示,键表示学生 ID,值用一个 set 表示,可以按升序存储所有课程编号。在读取学生信息的时候,将学生及其选课信息存入其中,查询时按要求输出即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ki, index, mi;
    cin >> ni >> ki;
    string id;
    unordered_map<string, set<gg>> ans;
    for (gg i = 0; i < ki; ++i) {
        cin >> index >> mi;
        for (gg j = 0; j < mi; ++j) {
            cin >> id;
            ans[id].insert(index);
        }
    }
    for (gg i = 0; i < ni; ++i) {
        cin >> id;
        auto& c = ans[id];
        cout << id << " " << c.size();
        for (auto j : c) {
            cout << " " << j;
        }
        cout << "\n";
    }
    return 0;
}