PAT Basic 1065 单身狗

  1. 云栖社区>
  2. 博客>
  3. 正文

PAT Basic 1065 单身狗

lovedan 2017-11-08 12:13:00 浏览642
展开阅读全文
  1. 单身狗(25)

时间限制
300 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
CHEN, Yue

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

输入格式:

输入第一行给出一个正整数N(<=50000),是已知夫妻/伴侣的对数;随后N行,每行给出一对夫妻/伴侣——为方便起见,每人对应一个ID号,为5位数字(从00000到99999),ID间以空格分隔;之后给出一个正整数M(<=10000),为参加派对的总人数;随后一行给出这M位客人的ID,以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式:

首先第一行输出落单客人的总人数;随后第二行按ID递增顺序列出落单的客人。ID间用1个空格分隔,行的首尾不得有多余空格。

输入样例:
3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333
输出样例:
5
10000 23333 44444 55555 88888

思路:把已婚人士记录到一个hash表中,互为对方id;查询阶段,每个query在已婚人士表中查看,没有查到则肯定单身,放到vector容器;查到了则放置到“等候区”,将其标记值设定为1;如果他/她配偶也在等候区那么她配偶的等候标记也等于1,那么两个人的等候标记都修改为2(表示双方都在场);随后遍历等候区,根据等候标记值是否等于1表示是否为单身狗,是则放入单身狗的vector容器。最后,单身狗的vector容器排序,再输出结果。

注意如果没有单身狗则不要输出多余换行。题目不说这点略坑。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <set>
#include <iomanip>
#include <sstream>
#include <unordered_map>

using namespace std;


int main() {
    unordered_map<string, string> mp;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;
        mp[a] = b;
        mp[b] = a;
    }
    int k;
    cin >> k;
    vector<string> v_dog;
    unordered_map<string, int> wait_region;
    for (int i = 0; i < k; i++) {
        string q_id;
        cin >> q_id;
        if (mp[q_id] == "") {
            v_dog.push_back(q_id);
        }
        else {
            wait_region[q_id] = 1;
            if (wait_region[mp[q_id]] == 1) {
                wait_region[q_id] = 2;
                wait_region[mp[q_id]] = 2;
            }
        }
    }
    unordered_map<string, int>::iterator it = wait_region.begin();
    for (; it != wait_region.end(); it++) {
        if (it->second == 1) {
            v_dog.push_back(it->first);
        }
    }

    cout << v_dog.size() << endl;
    sort(v_dog.begin(), v_dog.end());
    for (int i = 0; i < v_dog.size(); i++) {
        if (i > 0) {
            cout << " ";
        }
        cout << v_dog[i];
    }
    if (v_dog.size() > 0) {
        cout << endl;
    }
    
    return 0;
}

/*
使用了unordered_map来做,其实用数组也OK,只不过哈希表对于字符串类型id也适用。
第一个坑:结果要排序
第二个坑:如果单身狗数量为0,则不应该输出换行。题目居然不说这一点,好坑
*/

网友评论

登录后评论
0/500
评论
lovedan
+ 关注