题目描述

浙江大学有 40000 名学生，提供 2500 门课程。

现在给定每个学生的选课列表。

请你统计，每门课程的学生报名情况。

输入格式
第一行包含两个整数 N 和 K，分别表示学生总数和课程总数。

接下来 N 行，每行包含一个学生的选课列表，首先包含学生姓名（三个大写字母加一位数字），然后包含一个整数 C，表示该学生报课总数，接下来包含 C 个整数，表示所报课程编号。

所有课程编号为 1∼K。

输出格式
按照课程编号升序的顺序输出每一门课的报名情况。

每门课输出信息时，第一行包含两个整数，分别表示课程编号以及报名人数。

接下来若干行，按字典序输出报名的具体人员姓名，每个姓名占一行。

数据范围
1≤N≤40000,
1≤K≤2500,
1≤C≤20,

输入样例：

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

输出样例：

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

算法1

(暴力io) $O(n)$

使用cin,cout 和 ios::sync_with_stdio(false),cin.tie(0);
这个可以在AcWing上通过，无法在PAT上过。

时间复杂度

参考文献

C++ 代码

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    vector<string> curse[n+1];
    string name;
    for(int i=0;i<n;i++)
    {
        cin>>name;
        int p; scanf("%d",&p);
        for(int i=0;i<p;i++)
        {
            int lei;
            scanf("%d",&lei);
            curse[lei].push_back(name);
        }
    }
    for(int i=1;i<=k;i++)
    {
        printf("%d %d\n",i,curse[i].size());
        sort(curse[i].begin(),curse[i].end());
        for(auto x:curse[i])
            cout<<x<<endl;
    }

    return 0;
}

算法2

(scanf,printf优化) $O(n)$

使用scanf,printf和(string).c_str()的输出方法，大大减少了运算时间，就可以通过了。

时间复杂度

参考文献

C++ 代码

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

int main()
{   
    int n,k;
    scanf("%d%d",&n,&k);
    vector<string> curse[n+1];
    for(int i=0;i<n;i++)
    {
        char tem[5];
        int p; scanf("%s%d",tem,&p);
        string name(tem);
        for(int i=0;i<p;i++)
        {
            int lei;
            scanf("%d",&lei);
            curse[lei].push_back(name);
        }
    }
    for(int i=1;i<=k;i++)
    {
        printf("%d %d\n",i,curse[i].size());
        sort(curse[i].begin(),curse[i].end());
        for(auto x:curse[i])
            printf("%s\n", (x).c_str());
    }

    return 0;
}