题目描述
浙江大学有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;
}
···
