PAT (Advanced Level) 1047. Student List for Course (25) 哈希，排序，string與char數組的轉換

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      

寫一個哈希表vector<vector<string> > hashx(K+1)；hashx[i]存儲課程i的所有學生。      

由于輸出時學生要按照姓名排序。有兩種方法，一是哈希後，對哈希表的單個元素，即單個課程内的學生進行排序。二是先對輸入資料進行排序，然後進行哈希，這種方法隻需要排序一次，效率較高。      

為避免逾時，輸入輸出使用C語言寫。注意C語言char數組與C++string的互相轉換，用char數組初始化string即可轉為string，而strcpy(ch,s.c_str());可将string對象s轉為char數組ch。      

/*2015.7.26cyq*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;

struct stu{
	string name;		//學生姓名
	vector<int> course; //課程
	bool operator < (const stu &a)const{
		return name<a.name;
	}
};
int main(){
	int N,K;
	scanf("%d%d",&N,&K);
	vector<stu> data;
	int C;
	int x;
	char ch[5];
	while(N--){
		stu tmp;
		scanf("%s",ch);
		tmp.name=ch;	//char數組轉string
		scanf("%d",&C);
		while(C--){
			scanf("%d",&x);
			tmp.course.push_back(x);
		}
		data.push_back(tmp);
	}
	sort(data.begin(),data.end());//對學生按照字母進行排序
	
	vector<vector<string> > hashx(K+1);//hashx[i]存儲課程i的所有學生
	for(auto it=data.begin();it!=data.end();it++){
		for(auto ik=(*it).course.begin();ik!=(*it).course.end();ik++){
			hashx[*ik].push_back((*it).name);
		}
	}
	for(int i=1;i<=K;i++){
		if(!hashx[i].empty()){//該課程有學生
			printf("%d %d\n",i,hashx[i].size());
			for(auto it=hashx[i].begin();it!=hashx[i].end();++it){
				strcpy(ch,(*it).c_str());//string轉char數組
				printf("%s\n",ch);
			}
		}else{
			printf("%d 0\n",i);
		}
	}
	return 0;
}