1039. Course List for Student (25)-白红宇

1039. Course List for Student (25)

阅读量：4150 次

发布时间：2019-05-25

本文共 1563 字，大约阅读时间需要 5 分钟。

倒排索引题

这道题目好像是为数不多的一道卡时题，你在PAT刷的很happy的时候，还是要注意下string的滥用的。

因为string的拷贝以及比较操作都要比char数组相同操作的效率低。

另外其实vector的频繁改变数组大小其实也比较耗时，不过在PAT上还是都可以用vector的。

#include
   
    #include
    
     #include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;vector
           
             name2course[26*26*26*10];int main(){ //input int n, k; scanf("%d%d",&n,&k); //if use string instead of char*, then will be TLE, the copy time is also a bottle neck //may be if we do not use vector container and just use array, may be string can be used //in such a TLE case, every where we use STL container or cin/cout it can be a bottle neck vector
            
             
              > course(k+1); for(int i = 0; i < k; ++i) { int cid, num; scanf("%d%d",&cid,&num); course[cid].resize(num); for(int j = 0; j < num; ++j) { char* name = new char[4]; scanf("%s",name); course[cid][j] = name; } } //build the map for(int i = 1; i <= k; ++i) { for(int j = 0; j < course[i].size(); ++j) { char* name = course[i][j]; int index = (name[0]-'A')*26*26*10+(name[1]-'A')*26*10+(name[2]-'A')*10+(name[3]-'0'); name2course[index].push_back(i); } } //for query for(int i = 0; i < n; ++i) { char name[4]; scanf("%s",name); printf("%s",name); int index = (name[0]-'A')*26*26*10+(name[1]-'A')*26*10+(name[2]-'A')*10+(name[3]-'0'); printf(" %d", name2course[index].size()); for(int j = 0; j < name2course[index].size(); ++j) { printf(" %d", name2course[index][j]); } printf("\n"); } //release for(int i = 0; i < course.size(); ++i) { for(int j = 0; j < course[i].size(); ++j) { delete[] course[i][j]; } } return 0;}