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

1047. Student List for Course 题目描述:

给出每个学生的注册课程的信息, 要求输出每个课程的注册学生列表.

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.

1047. Student List for Course 算法分析:

基本上是一个倒排表的思想, 扫一遍输入, 正对每个课程, 都挂一个学生名字的list. 输出的时候, 先对这个学生姓名list排序, 然后输出即可, 注意可能需要用到内存压缩, 不要直接对名字进行排序, 把学生的名字压缩到一个整型变量里面再排序, 否则可能会超时. AC代码如下:

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> course[2501];

int main()
{
    int n,k;
    char name[10];
    int nc, c;
    int hashv;
    scanf("%d %d", &n, &k);

    for(int i=0;i<n;i++)
    {
        scanf("%s %d", name, &nc);
        hashv = (name[0]<<24) + (name[1]<<16) + (name[2]<<8) + name[3];
        for(int j=0;j<nc;j++)
        {
            scanf("%d", &c);
            course1.push_back(hashv);
        }
    }
    for(int i=1;i<=k;i++)
    {
        printf("%d %d\n", i, course[i].size());
        sort(course[i].begin(), course[i].end());
        for(int j=0;j<course[i].size();j++) {
            hashv = course[i][j];
            printf("%c%c%c%c\n",
                    (hashv & 0xff000000) >> 24,
                    (hashv &   0xff0000) >> 16,
                    (hashv &     0xff00) >> 8,
                    hashv & 0xff);
        }
    }
    return 0;
}

1047. Student List for Course 注意点:

不要用cin, cout, 学生名字需要压缩, 否则都会造成TLE.

Written on January 19, 2014