PAT 1039 Course List for Student (25分) 使用map

PAT 1039 Course List for Student (25分) 使用map>

2020 年 6 月 10 日
筆記
C/C++, C++, map, PAT, 數據結構與演算法, 演算法與數據結構

題目

Zhejiang University has 40000 students and provides 2500 courses. Now given the student name lists of all the courses, you are supposed to output the registered course list for each student who comes for a query.

Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤40,000), the number of students who look for their course lists, and K (≤2,500), the total number of courses. Then the student name lists are given for the courses (numbered from 1 to K) in the following format: for each course i, first the course index i and the number of registered students Ni (≤200) are given in a line. Then in the next line, Ni student names are given. A student name consists of 3 capital English letters plus a one-digit number. Finally the last line contains the N names of students who come for a query. All the names and numbers in a line are separated by a space.

Output Specification:
For each test case, print your results in N lines. Each line corresponds to one student, in the following format: first print the student’s name, then the total number of registered courses of that student, and finally the indices of the courses in increasing order. The query results must be printed in the same order as input. All the data in a line must be separated by a space, with no extra space at the end of the line.

Sample Input:

11 5
4 7
BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
1 4
ANN0 BOB5 JAY9 LOR6
2 7
ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6
3 1
BOB5
5 9
AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9

Sample Output:

ZOE1 2 4 5
ANN0 3 1 2 5
BOB5 5 1 2 3 4 5
JOE4 1 2
JAY9 4 1 2 4 5
FRA8 3 2 4 5
DON2 2 4 5
AMY7 1 5
KAT3 3 2 4 5
LOR6 4 1 2 4 5
NON9 0

題目大意

有K個課程，給出每個課程的編號，選課人數，這些人的名字
有N個學生來查詢他們的選課列表，按輸入順序處理每個人的查詢請求，輸出他的姓名選課數目課程1編號課程2編號 …，要求課程編號輸出順序滿足從小到大。

思路分析

既然要得到每個學生的選課列表，而給出的學生姓名是字元串，要求輸出的課程編號是整數，那就用一個 map<string, vector<int>>存儲，其中，鍵是學生姓名，值是學生選課列表。

我們需要做的就是在讀取輸出過程中，轉換輸入（每個課程選課的有哪些人）轉換成學生以及對應的選課列表。

這個很簡單，就是「對號入座」。

比如對於輸入中某一個課的情況，1號課，4個人選了，姓名分別如下

1 4
ANN0 BOB5 JAY9 LOR6

只需要這樣簡單處理

// 課號和選課人數
cin >> cno >> cnum;
// 選課的都是哪些人
while(cnum-- > 0) {
    // 選課人名字
    cin >> name;
    // 記錄，這個人，選了這個課
    stu_cource[name].push_back(cno);
}

之後要查詢某個學生的選課列表，只需要map[name]就能得到他的選課列表vector<int>，為了滿足輸出要求，對vector<int>進行一次sort()即可。

完成程式碼

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

// 保存每個學生和他的選擇列表
map<string, vector<int>> stu_cource;

int main() {
    // N個學生要查詢，K個課
    int N, K;
    cin >> N >> K;
    // 每個課的編號，選課人數
    int cno, cnum;
    string name;
    while (K-- > 0) {
        // 課號和選課人數
        cin >> cno >> cnum;
        // 選課的都是哪些人
        while(cnum-- > 0) {
            // 選課人名字
            cin >> name;
            // 記錄，這個人，選了這個課
            stu_cource[name].push_back(cno);
        }
    }
    // N個人查詢
    while(N-- > 0) {
        cin >> name;
        // 得到他的選課列表
        vector<int> course = stu_cource[name];
        // 課號按順序排
        sort(course.begin(), course.end());
        // 輸出 姓名 幾個課 課號1 課號2 ...
        cout << name << " " << course.size();
        for (int cno: course) 
            cout << " " << cno;
        cout << endl;
    }
    return 0;
}

Tags: C/C++ C++ map PAT 數據結構與演算法演算法與數據結構