从一道简单的题看算法优化 ZOJ PAT Course List for Student
一位好友保研后突然想做做ZOJ的PAT Practise，据说里面的题都比较水，但是还是不幸的卡在了Course List for Student (25)上面。
这是PAT的链接：http://pat.zju.edu.cn/contests/pat-practise
【题目大意】
浙大有40000名同学和2500个课程。给出每门课的选课名单，现在有N个同学要查询他们的选课列表，请输出每个人的选课结果。
先给出n（n <= 40000 ）和m（m<=2500），n表示要查询选课名单的人数，m代表总共的课程数。
接着给出m个课程的选课名单，格式如下：
x（x<=2500）代表该课程的编号，y（y<=200）代表选该课程的人数，接着输出这y个人的姓名。
最后给出n个学生的姓名，输出每个姓名的选课名单，按课程编号从小到大输出。
姓名由4个字符组成，前3个为大写字母，第四个为一个数字。
内存限制【32M】，时间限制【200ms】
【分析】
如果不考虑数据量，建一个<姓名，课程>的二维表来查询，对于每个查询，只需要输出其后的课程编号即可，显然这里用二维矩阵远远超过内存限制（32M）。同时，最多只有2500*200=500,000个选课数据，总大小40000*2500=100,000,000，有效利用率仅0.5%。
于是可以采用map<string,vector<int> >的格式进行储存，键对应姓名，vector对应该姓名的选课编号。输入完毕后对每个姓名后的选课编号进行排序，然后依照查询输出。
这种时间算法复杂度太高。排序时间为为O(nmlog(m))，每次查询时间O(logn*m)，总查询O(nmlog(n))。
查询的效率低下，问题出在对每个姓名都需要进行一次排序，或者提前将所有人员的选课名单都进行排序，显然这两种方法时间复杂度太高。
如果采用计数排序，总时间复杂度略微减少，不过依然是TLE。
进一步分析：
考虑将姓名和课程组成某种数据结构，只进行一次排序即可通过某种方式找出。
由于是对某人选课的课程序号排序，且课程序号至多为2500，于是将<姓名编号，课程编号>压缩成一个id，
id = 姓名编号*2500 + 课程编号。
显然，如此排序后，某人的选课课程必然在[2500*该生姓名编号+1,2500*该生姓名编号+2500]之间。于是对所有id排序一次，然后二分出边界，边界范围内的值即为该生的选课课程编号。
时间复杂度O(plog(p)+nlog(p)) (p<=500,000,n<=40000)
【总结】
进过简单的压缩可以将排序次数从n次减少为1次，说明数据的组织方式即为重要！
【代码】
#include <stdio.h>#include <map>#include <set>#include <string.h>#include <string>#include <algorithm>#include <vector>using namespace std;bool get(int& a){if( scanf("%d",&a) == EOF ) return false ;return true ;}const int maxn = 2500*200 ;int nimei[maxn] , cnt ;int id[26][26][26][10] ;int bs(int key,int l,int r){int mid ;while ( l <= r ){mid = ( l + r ) >> 1 ;if( nimei[mid] > key )r = mid - 1 ;else l = mid + 1 ;}return r ;}int main(){int n , m ;get(n); get(m);int i , j , k ;int idCnt = 1 ;cnt = 0 ;for ( i = 0 ; i < m ; i++){get(j); get(k);char str[16] ;while(k--){scanf("%s",str);int &temp = id[str[0]-'A'][str[1]-'A'][str[2]-'A'][str[3]^48] ;if( temp == 0 )temp = idCnt++;nimei[cnt++] = ( temp << 12 ) | j ;}}sort(nimei,nimei+cnt);char name[16] ;while(n--){scanf("%s",name);int t = id[name[0]-'A'][name[1]-'A'][name[2]-'A'][name[3]^48] ;if( t == 0 ){printf("%s 0\n",name);continue;}j = bs(t<<12,0,cnt-1) ;k = bs((t+1)<<12,j,cnt-1);printf("%s %d",name,k-j);for ( j++; j <= k ; j++){printf(" %d",nimei[j] &0x00000fff);}puts("");}}