1039. Course List for Student (25)

时间限制

200 ms

内存限制

32000 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

Zhejiang University has 40000 students and provides 2500 courses. Now given the student name lists of all the courses, you are supposed to output the registered course list for each student who comes for a query.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: N (<=40000), the number of students who look for their course lists, and K (<=2500), the total number of courses. Then the student name lists are given for the courses (numbered from 1 to K) in the following format: for each course i, first the course index i and the number of registered students N_i (<= 200) are given in a line. Then in the next line, N_i student names are given. A student name consists of 3 capital English letters plus a one-digit number. Finally the last line contains the N names of students who come for a query. All the names and numbers in a line are separated by a space.
Output Specification:
For each test case, print your results in N lines. Each line corresponds to one student, in the following format: first print the student’s name, then the total number of registered courses of that student, and finally the indices of the courses in increasing order. The query results must be printed in the same order as input. All the data in a line must be separated by a space, with no extra space at the end of the line.
Sample Input:

11 5
4 7
BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
1 4
ANN0 BOB5 JAY9 LOR6
2 7
ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6
3 1
BOB5
5 9
AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9

Sample Output:

ZOE1 2 4 5
ANN0 3 1 2 5
BOB5 5 1 2 3 4 5
JOE4 1 2
JAY9 4 1 2 4 5
FRA8 3 2 4 5
DON2 2 4 5
AMY7 1 5
KAT3 3 2 4 5
LOR6 4 1 2 4 5
NON9 0

=================================
PAT上通过率0.09的题目看着挺可怕
主要是时间的问题我想，做那么多次查询~
第一想法是直接用STL的map给名字做索引
这样的话搜索效率是O(log2n)，因为map是用神马树实现的
不过…后来想想这个题目那么多跪了的，估计肯定不能用这个
只能拿空间换时间了~
权衡了一下，因为姓名是3个字母加1个数字，所以可以自己写个浪费空间的Hash函数，将名字的字母部分映射成数组的索引
哈希了一下嘛，时间复杂度就是O(1)了，邪恶一笑…
数组使用map>实现，显然前面那个int就是给字母最后的数字使用的，后面那个存的course的ID
这样可能稍微能节约点空间，不然26*26*26*10需要175760那么多地方…浪费地有点多
其他没有什么可以说的，里头有现成的sort，专门对付STL容器里头的排序，自己写个compare函数就行了，相当方便。
提交一次通过，虽然最长时间是180ms有点危险，不过不想再去折腾这个了。
==================================

#include 
#include 
#include 
#include 
using namespace std;
map< int, vector> stu_cou_map[17576];
inline int GetHashIndex(char name[])
{
	//给出一个名字比如BOB5，得到对应 stu_cou_map的索引号
	int index = 676 * (name[0] - 0x41) + 26 * (name[1] - 0x41) + (name[2] - 0x41);
	return index;
}
inline bool mySortFunc (int i, int j)
{
	return (i s;
				s.push_back(course_id);
				stu_cou_map[index].insert( pair>(suffix, s));
			}
			else
			{
				stu_cou_map[index][suffix].push_back(course_id);
			}
		}
	}
	for(int i=0; i s = stu_cou_map[index][suffix];
		printf(" %d", s.size());
		vector::iterator begin = s.begin();
		vector::iterator end = s.end();
		sort(begin, end, mySortFunc);
		for(vector::iterator it = begin; it!=end; it++)
		{
			printf(" %d", *it);
		}
		printf("n");
	}
	return 0;
}

==========================================
测试点结果用时(ms) 内存(kB) 得分/满分
0 答案正确 0 1250 15/15
1 答案正确 0 1380 2/2
2 答案正确 0 1380 2/2
3 答案正确 0 1380 2/2
4 答案正确 0 1380 2/2
5 答案正确 180 21700 2/2

1039. Course List for Student (25)

Leave a Reply Cancel reply