PAT 解题报告1039. Course List for Student (25)

1039. Course List for Student 题目描述:

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.

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 Ni (<= 200) are given in a line. Then in the next line, Ni 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.

题目要求给出K个课程的注册学生(Registered Students)信息, 每个课程最多Ni <= 200 个注册学生, 然后针对若干个学生(N个)做查询, 查出这些个学生每一个都选了哪些课.

1039. Course List for Student 算法分析:

这个题目一般的算法其实不难想到, 但是想要通过, AC起来却相当不容易. 首先很容易想到倒排表(Inverted Index)之类的数据结构map< string, set >  theMap, 这里的key就是学生的姓名, set就是对应的这个学生选的课程, 这个倒排表的制作过程很简单, 扫一遍输入数据, 对每一个课程id下面的所有student name 都做一次 theMap[student name].insert(id) . 那么最多有K \* Ni <= 2500 \* 200 = 500000次这样的操作. 然后就是做查询了, 每次来一个student name, 我们就找到theMap[student name]输出所有的课程id. 这个思路似乎很简单, 但是仔细分析一下确实是过不了OJ的. 原因如下: (1) 假设这个map和set都是Hash算法做的, 那么时间上, 均摊的插入或者搜索时间都是O(1)常数时间, 于是制作这个表需要O(Ni \* K)的时间, 查询就O(N \* 常数时间), 时间上应该是受得了的, 但是空间上就不一定了, 首先我们至少有500000 \* 8Byte = 4000KB内存, id用int是四个字节, 每个学生的名字也是四个字节, 但是一般我们用Hash的话就是用空间换时间, 4000KB的内存是那种装载因子是100%的情况下也需要的最少内存, 对于哈希表来说, 装载因子肯定不大, 于是实际的内存就是4000KB / alpha, 其中alpha是哈希表的装载因子 < 1. 然后想想题目允许的最大内存是32000KB, 这样就相当容易爆内存了, 也就是exceeds memory limit. (2) 假设使用平衡二叉树实现的map和set. 那么建立倒排表的时间就是O(K \* Ni \* logN \* logNi), 查询的时间就是O(NlogNi). 首先时间复杂度更高, 其次, 经过验证还是爆了内存, 这里具体原因尚且不明, 但是猜测和C++STL的性能有关.  总是理论分析和实践都证明倒排表的思路不可行.

于是我们 只能求助于内存压缩了. 把学生姓名和课程id信息组织到一个int型的数据里面压缩存储: 学生的名字总是由大写字母和数字表示的, 那么把学生名字当成26进制的数字每个学生姓名都可以转换成一个唯一的十进制数字sid, 然后课程id (called cid here)也是从1到2500的十进制数, 于是数值gid = sid * 2500 + cid –  1 就可以唯一表示某个学生 (gid / 2500) 选了某门课程( gid % 2500). 那么我们可以根据输入得到最多500000个这样的gid, 然后我们排序, 当给出一个查询学生的名字的时候, 我们先得到sid, 然后这个学生选的课一定是在sid * 2500 到 (sid + 1)* 2500 之间的那些gid所储存的课程信息. 所以我们只要二分法搜索这两个界就可以得到sid对应的所有gid, 最后解析出课程的cid. 实现代码如下, 可以AC:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#define REP(i,n) for(int i=0;i<(n);++i)

#define twosix23 17576
#define twosix22 676
#define twosix21 26
#define maxk 2500

using namespace std;

int N, K;
vector<int> gids;

int bs(int gg) {
    int l = 0;
    int r = gids.size()-1;
    int mid;
    while(l <= r) {
        mid = (l+r)/2;
        if(gg < gids[mid]) r = mid -1;
        else l = mid + 1;
    }
    return r;
}

int main(void) {
    scanf("%d %d", &N, &K);
    int id, nstu;
    char name[5];
    REP(i, K) {
        scanf("%d %d", &id, &nstu);
        REP(j, nstu) {
            scanf("%s", name);
            int gid = 0;
            gid = (name[0]-'A')*twosix23 + (name[1]-'A')*twosix22
                    + (name[2]-'A')*twosix21 + (name[3]-'0');
            gid = gid * maxk + id - 1;
            gids.push_back(gid);
        }
    }
    sort(gids.begin(), gids.end());
    REP(i, N) {
        scanf("%s", name);
        int sid = 0;
        sid = (name[0]-'A')*twosix23 + (name[1]-'A')*twosix22
            + (name[2]-'A')*twosix21 + (name[3]-'0');
        int gg = sid * maxk - 1;
        int j = bs(gg);

        gg = sid * maxk + 2499;
        int k = bs(gg);
        printf("%s %d", name, k-j);
        for(j++; j<=k; ++j) printf(" %d", gids[j]%2500 + 1);
        printf("\n");
    }
    return 0;
}

1039. Course List for Student 注意点:

倒排表的思路以及STL的map会爆内存.  第二, 实现二分搜索的边界条件要特别注意.

 

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on January 3, 2014