PAT A1047

Zhejiang University has 40000 students and provides 2500 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 (<=40000), the total number of students, and K (<=2500), 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include "stdio.h"
//#include "math.h"
#include "string.h"
//#include "iostream"
//#include "stdlib.h"
#include "algorithm"
#include "vector"
using namespace std;
//typedef long long LL;
const int maxn = 40010;//最大学生人数
const int maxk = 2510;//最大课程门数

char name[maxn][5];//maxn个学生
vector<int> course[maxk];//couse[i]存放第i门课的所有学生编号

bool cmp(int a, int b){
return strcmp(name[a], name[b]) < 0;//按姓名字典序从小到大排序
}
int main(){
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
int c, kc;
scanf("%s %d", name[i], &c);
for (int j = 0; j < c ; j++) {
scanf("%d", &kc);
course[kc].push_back(i);//读入一门课就把学生的ID写入课程之下
}
}
for (int i = 1; i <= k ; i++) {
printf("%d %d\n", i, course[i].size());
sort(course[i].begin(), course[i].begin() + course[i].size(), cmp);//名字从小到大排序
for (int j = 0; j < course[i].size(); j++) {
printf("%s\n", name[course[i][j]]);
}
}

return 0;
}

1、使用vector来存放每门课程的选课学生编号,可以有效防止所有学生选了所有课程的极端情况导致空间超限。而且vector的使用十分简便。
2、小技巧:如果排序时直接对字符串排序,那么会导致大量的字符串移动,非常消耗时间。
本题的做法是让二维数组char[n][5]存放输入的姓名,其中char[i]表示第i个姓名,在编写cmp函数的时候,每次输出课程下的学生时再按照字典序重新排序即可。
3、strcmp的返回值不一定是-1,0,+1,也有可能是其他正数和负数。所以这里写strcmp(name[a], name[b]) < 0更具有普适性。