【1039】 Course List for Student (25)

题目描述

浙江大学有40000个学生，并开2500门课，给出所有课程的学生列表，输出每个学生的课程列表

输入

第一行 n(<=4000,学生人数） k（<=2500,课程数）
随后2k行：
一行：cid (课程id 1~k） Ni(课程id的学生数
第二行：Ni个学生name（三个字母+一个数字构成）
第2k+1行为：
n个学生名字

输出：

按最后一行学生名字顺序输出（姓名，选修的课程数，课程id（需要按从小到大的顺序输出））

解题思路

将以学生姓名（string）为key，该生的课程列表(vector<int>)为value的map存储数据,并对value进行排序，并按照输入的名字顺序输出map的value.
但是这种方式会有一组数据超时，因此考虑将姓名不以string类型存储,将姓名以每个字母的ASCII码的形式计算转换为int类型（ t = (((name[0] - 'A') * 26 + (name[1] - 'A')) * 26 + name[2] - 'A') * 26 + name[3] - '0';
）.

代码

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int getkey(char *name) {
    int key = 0;
    for(int i = 0; i < 3; i++)
        key= 26 * key+ (name[i] - 'A');
    key= key * 10 + (name[3] - '0');
    return key;
}
int main() {
    int n, m;
    vector< vector<int> > students(175770);
    scanf("%d%d",&n, &m);
    int t;
    char name[5];
    int cid, cnums;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &cid, &cnums);
        for (int j = 0; j < cnums; j++) {
             scanf("%s",name);
             t = getkey(name);
             students[t].push_back(cid);
        }
    }   
    for (int i = 0; i < n; i++) {
         scanf("%s",name);
         t = getkey(name);
         printf("%s %lu", name, students[t].size());
         sort(students[t].begin(), students[t].end());
         for (int j = 0; j < students[t].size(); j++) {
            printf(" %d",students[t][j]);
        }
        printf("\n");
    }
        return 0;
}


···