題目描述

浙江大學(xué)有40000個(gè)學(xué)生，并開2500門課，給出所有課程的學(xué)生列表，輸出每個(gè)學(xué)生的課程列表

輸入

第一行 n(<=4000,學(xué)生人數(shù)） k（<=2500,課程數(shù)）
隨后2k行：
一行：cid (課程id 1~k） Ni(課程id的學(xué)生數(shù)
第二行：Ni個(gè)學(xué)生name（三個(gè)字母+一個(gè)數(shù)字構(gòu)成）
第2k+1行為：
n個(gè)學(xué)生名字

輸出：

按最后一行學(xué)生名字順序輸出（姓名，選修的課程數(shù)，課程id（需要按從小到大的順序輸出））

解題思路

將以學(xué)生姓名（string）為key，該生的課程列表(vector<int>)為value的map存儲(chǔ)數(shù)據(jù),并對(duì)value進(jìn)行排序，并按照輸入的名字順序輸出map的value.
但是這種方式會(huì)有一組數(shù)據(jù)超時(shí)，因此考慮將姓名不以string類型存儲(chǔ),將姓名以每個(gè)字母的ASCII碼的形式計(jì)算轉(zhuǎn)換為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;
}


···