---

题196.pat甲级练习-1047 Student List for Course (25 分)

---

一、题目

二、题解

输入时将名字入到对应课程表示的容器下就好，最最需要注意的是，输入输出只能想办法用scanf和printf，不然一定会超时。下面是用set来装人名的代码，仍然超时了就是了，后面会给出正确代码。

//用set仍然超时，insert会多耗时间的
#include <bits/stdc++.h>using namespace std;set<string> s[2501];int main()
{int N,K;scanf("%d%d",&N,&K);for(int i=0;i<N;i++){char name[5];//为避免超时，所以我输入只能用scanf，所以不得不用char []scanf("%s",name);int C;scanf("%d",&C);for(int j=0;j<C;j++){int course;scanf("%d",&course);s[course].insert(name);//string(char[])，可将char[]通过构造方法变成string。这里直接insert就好，因为set<string>}}for(int i=1;i<=K;i++){printf("%d %d\n",i,s[i].size());//输出课程编号和课程人数for(auto it=s[i].begin();it!=s[i].end();it++){printf("%s\n",(*it).c_str());//将string用.c_str()转成char[]用printf输出，不能用cout否则会超时}}
}

把set改成vector去装，之后排序就好了。代码如下：

#include <bits/stdc++.h>using namespace std;vector<string> v[2501];int main()
{int N,K;cin>>N>>K;for(int i=0;i<N;i++){char name[5];scanf("%s",name);int C;scanf("%d",&C);for(int j=0;j<C;j++){int c;scanf("%d",&c);v[c].push_back(name);}}for(int i=1;i<=K;i++){printf("%d %d\n",i,v[i].size());sort(v[i].begin(),v[i].end());for(int j=0;j<v[i].size();j++){printf("%s\n",v[i][j].c_str());}}
}

用set不超时(巧用运算符重载，在输入时就做好排序，后期直接倒腾，不必再字典排序)，可以这么干，代码如下:

/*
#include <bits/stdc++.h>using namespace std;
struct stuInfo{char name[5];int C;int course[20];bool operator < (const stuInfo &x) const{return strcmp(name,x.name) <= 0;}bool operator > (const stuInfo &x) const{return strcmp(name, x.name) >= 0;}bool operator == (const stuInfo &x) const{return strcmp(name, x.name) == 0;}
};
set<stuInfo> s;
vector<string> courses[2501];
int main()
{int N, K;scanf("%d%d", &N, &K);stuInfo *stu;for (int i = 0; i < N; i++){stu=new stuInfo();scanf("%s", stu->name);scanf("%d", &stu->C);for (int j = 0; j < stu->C; j++){scanf("%d", stu->course+j);}s.insert(*stu);}for(auto it=s.begin();it!=s.end();it++)//由于前面insert操作把名字按字典序排好了所以这里直接倒腾{for(int i=0;i<it->C;i++)//访问那个人结构体，将它选的课程插入他的名字（不用担心课程的人名字字典序了，因为字典序在前的会先被拿来插入）{courses[it->course[i]].push_back(it->name);}}for (int i = 1; i <= K; i++){printf("%d %d\n", i, courses[i].size()); //输出课程编号和课程人数for (auto it = courses[i].begin(); it != courses[i].end(); it++){printf("%s\n", (*it).c_str()); //将string用.c_str()转成char[]用printf输出，不能用cout否则会超时}}
}
*/

---