PAT A1039 unordered_map

使用cin和cout会超时，为了加快速度，可以加上ios::sync_with_stdio(false);map是基于红黑树实现的，unordered_map是基于哈希实现的，对于本题来说，由于不需要对元素进行排序，显然使用unordered_map下面为代码和注解#include <iostream>#include <vector>#include <unorde

R_0nnie

138人浏览 · 2020-06-24 12:08:54

R_0nnie · 2020-06-24 12:08:54 发布

使用cin和cout会超时，为了加快速度，可以加上

ios::sync_with_stdio(false);

map是基于红黑树实现的，unordered_map是基于哈希实现的，对于本题来说，由于不需要对元素进行排序，显然使用unordered_map

下面为代码和注解

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<int> stu[180000];
unordered_map<string, int> mp;
int cnt;  // cnt为不同学生代表的不同编号

int main()
{
    ios::sync_with_stdio(false);

    int num, T;
    cin >> num >> T;
    while(T --)
    {
        int cur, n;
        cin >> cur >> n;

        while(n --)
        {
            string s;
            cin >> s;
            if (mp.count(s) == 0)
                mp[s] = cnt ++;  //如果没有此学生，则将其对应cnt，cnt++
            int x = mp[s];
            stu[x].push_back(cur);
        }
    }

    while(num --)
    {
        string s;
        cin >> s;
        cout << s << ' ';
        if (mp.count(s) == 0)
            cout << 0 << endl;
        else
        {
            int x = mp[s];
            sort(stu[x].begin(), stu[x].end());

            cout << stu[x].size() ;
            for (auto item:stu[x])
                cout << ' '<< item ;
            cout << endl;
        }
    }

    return 0;
}