【PAT甲级】Student List for Course

喜欢ctrl的cxk

发布于 2019-11-08 10:41:14

3020

发布于 2019-11-08 10:41:14

文章被收录于专栏：Don的成长史

                 本文链接：[https://blog.csdn.net/weixin\_42449444/article/details/90610725](https://blog.csdn.net/weixin_42449444/article/details/90610725)

Problem Description：

Zhejiang University has 40,000 students and provides 2,500 courses. Now given the registered course list of each student, you are supposed to output the student name lists of all the courses.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤40,000), the total number of students, and K (≤2,500), the total number of courses. Then N lines follow, each contains a student's name (3 capital English letters plus a one-digit number), a positive number C (≤20) which is the number of courses that this student has registered, and then followed by C course numbers. For the sake of simplicity, the courses are numbered from 1 to K.

Output Specification:

For each test case, print the student name lists of all the courses in increasing order of the course numbers. For each course, first print in one line the course number and the number of registered students, separated by a space. Then output the students' names in alphabetical order. Each name occupies a line.

Sample Input:

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

Sample Output:

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

解题思路：

我看完这道题的题目之后，第一反应就是我好像刷过这题，特别有印象！我写完之后还觉得把map和vector结合起来用特别酷。然而PTA上显示我并没做过这道题，仔细一看发现这题只是跟【PAT甲级】Course List for Student特别像，就是把输入输出颠倒了一下。说下这题的思路吧：先建立一个map<int, vector<string> > m，m的key是课程号，m的value是个string型的vector，它用来存放选择该课程号的所有学生的姓名。无脑for-each遍历所有的课程号，输出每个课程号以及选择该课程的学生人数，再将选择该课程的所有学生按照姓名升序排列以后输出即可。然而！提交代码后出现了WA，25分只得了22分。

冷静分析了一波之后，我发现代码错在哪里啦：当某个课程 i 没有学生选择的时候，预期输出应该是" i 0"，但是实际输出的结果却直接跳过了这个没有学生选择的课程 i 。原因很简单map中并没有存放这个课程。于是我把对map的for-each语句改成了一个从1到K(K为课程数)的for循环，然后对选择每个课程的学生按照姓名进行升序排列后无脑for-each输出即可。提交代码能AC。

AC代码： 22分代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);  //取消cin和stdin的同步
    int N,K;
    cin >> N >> K;
    map<int, vector<string> > m;
    while(N--)
    {
        string name;
        int C;   //该学生选择的课程数
        cin >> name >> C;
        while(C--)
        {
            int id;   //该学生选择的课程号id
            cin >> id;
            m[id].push_back(name);
        }
    }
    for(auto it : m)   //遍历每个课程号,并输出选择该课程的学生
    {
        printf("%d %d\n", it.first, it.second.size());
        sort(it.second.begin(),it.second.end());   //根据学生姓名升序排列
        for(int i = 0; i < it.second.size(); i++)
        {
            printf("%s\n", it.second[i].c_str());
        }
    }
    return 0;
}

AC代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);  //取消cin和stdin的同步
    int N,K;   //学生数N,课程数K
    cin >> N >> K;
    map<int, vector<string> > m;
    while(N--)
    {
        string name;  //学生姓名
        int C;        //该学生选择的课程数C
        cin >> name >> C;
        while(C--)
        {
            int id;   //该学生选择的课程号id
            cin >> id;
            m[id].push_back(name);
        }
    }
    for(int i = 1; i <= K; i++)   //遍历每个课程号,并输出选择该课程的学生
    {
        printf("%d %d\n", i, m[i].size());
        sort(m[i].begin(),m[i].end());   //根据学生姓名升序排列
        for(auto it : m[i])  //无脑for-each输出选择该课程的学生姓名
        {
            printf("%s\n", it.c_str());
        }
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/05/27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

contains