（PAT)1047 Student List for Course (哈希的应用)

落日映苍穹つ 2022-05-10 00:14 134阅读 0赞

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

### 解题思路: ###

const int maxn = 40010;  //学生数量
    const int maxc = 2510;   //课程数量
    
    char name[maxn][5];  //学生表
    vector<int> course[maxc];  //存放第i门课所有学生编号

我们可以构建两个表,第一个表用来存储学生的姓名,maxn数组后缀可以用来作为学生的ID

第二个表是课程表,用来存储各课程所报名参加的学生(存储在vector<int>中) maxn数组后缀可以用来作为课程ID

我们可以把输入的学生用先定义一个标识,并把这个标识作为数组索引来存储学生名

然后再把这个标识放到对应的课程容器中去

int i = 0;
    	for (; i < n; ++i) {
    		int scours;
    		scanf("%s %d", name[i], &scours);
    		for (int j = 0; j < scours; ++j) {
    			int cno;
    			scanf("%d",&cno);
    			course[cno].push_back(i);   //存放第i门课所有学生编号
    		}
    	}

输出时,我们按顺序输出课程号和报名学生的数量

然后根据题意按照字典序输出学生名

这里先要对学生名排序,我们可以写一个元函数

bool cmp(int a, int b) {
    	return strcmp(name[a], name[b]) < 0;   //名字按照字典序排序
    }

然后进行排序

sort(course[i].begin(), course[i].end(), cmp);

然后输出就可以了

for (int i = 1; i <= k; ++i) {
    		printf("%d %d\n", i, course[i].size());
    		sort(course[i].begin(), course[i].end(), cmp);  //按照字典序排序
    		for (int j = 0; j < course[i].size(); ++j) {
    			printf("%s\n", name[course[i][j]]);
    		}
    	}