【算法笔记】A1039 Course List for Student

佚名 6年前 (2019-04-11) 随笔 1634人围观抢沙发百度已收录

https://pintia.cn/problem-sets/994805342720868352/problems/994805447855292416

题意：

　　有N个学生，K节课。给出选择每门课的学生姓名，，并在之后给出这N个学生姓名，按顺序输出每个学生选了几门课、哪几门课。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路：

　　用hash表存储每个学生的选课情况，需要定义一个hash函数把姓名转换为数字。查询时先把课程用sort()排序再输出。

　　最后一个测试点408ms，把 string name 改成 char name[] 之后106ms，说明大部分情况下string比较耗时。只有个别情况下char型数组会比较耗时。传送门

code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 26 * 26 * 26 * 10;
 4 const int N = 40010;
 5 vector<int> selectCourse[maxn];
 6 int getID(string name){
 7     int id = 0;
 8     for(int i = 0; i < 3; i++){
 9         id = id * 26 + (name[i] - 'A');
10     }
11     id = id * 10 + name[3] - '0';
12     return id;
13 }
14 int main(){
15     string name;
16     int n, k;
17     scanf("%d %d", &n, &k);
18     for(int i = 0; i < k; i++){
19         int course, x;
20         scanf("%d %d", &course, &x);
21         for(int j = 0; j < x; j++){
22             cin>>name;
23             int id = getID(name);
24             selectCourse[id].push_back(course);
25         }
26     }
27     for(int i = 0; i < n; i++){
28         cin>>name;
29         int id = getID(name);
30         sort(selectCourse[id].begin(), selectCourse[id].end());
31         cout<<name<<" "<<selectCourse[id].size();
32         for(int j = 0; j < selectCourse[id].size(); j++){
33             printf(" %d", selectCourse[id][j]);
34         }
35         printf("\n");
36     }
37     return 0;
38 }