【PAT甲级 - C++题解】1121 Damn Single

1121 Damn Single

“Damn Single (单身狗)” is the Chinese nickname for someone who is being single. You are supposed to find those who are alone in a big party, so they can be taken care of.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 50,000), the total number of couples. Then N lines of the couples follow, each gives a couple of ID’s which are 5-digit numbers (i.e. from 00000 to 99999). After the list of couples, there is a positive integer M (≤ 10,000) followed by M ID’s of the party guests. The numbers are separated by spaces. It is guaranteed that nobody is having bigamous marriage (重婚) or dangling with more than one companion.

Output Specification:

First print in a line the total number of lonely guests. Then in the next line, print their ID’s in increasing order. The numbers must be separated by exactly 1 space, and there must be no extra space at the end of the line.

Sample Input:

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

Sample Output:

5
10000 23333 44444 55555 88888

题意

给定 n 对情侣/夫妻，然后再给定参加派对的 m 人信息，需要我们找出这 m 个人中哪些人是单身的或其伴侣没有来参加派对。

思路

具体思路如下：

1.先用一个哈希表 st 来存储每对情侣和夫妻的信息，将他们对应起来。

2.输入要参加派对的人，放入 set 中会帮我们自动进行排序。

3.判断派对中哪些人是单身的或其伴侣没有来参加，如果这个人和其伴侣都来了，则在容器中删除他们。

4.输出最终结果，注意行末不得有空格。

代码

#include<bits/stdc++.h>
using namespace std;
int n, m;
unordered_map<string, string> st;
set<string> p1, p2;
int main()
{
    //输入n对人
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string a, b;
        cin >> a >> b;
        st[a] = b, st[b] = a;
    }
    //输入参加派对的人
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        string x;
        cin >> x;
        p1.insert(x);
    }
    //判断哪些人在派对中的单独一个人的
    p2 = p1;
    for (auto& s : p1)
    {
        //必须该人和其伴侣都在派对中才不算单独一个人
        if (st.count(s) == 1 && p1.count(st[s]) == 1)
        {
            p2.erase(s);
            p2.erase(st[s]);
        }
    }
    //输出单身的人
    cout << p2.size() << endl;
    vector<string> res(p2.begin(), p2.end());
    if (res.size()) cout << res[0];
    for (int i = 1; i < res.size(); i++)   cout << " " << res[i];
    return 0;
}