PAT(A) 1121. Damn Single (25)

原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1121

1121. Damn Single (25)

---

"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 (<=50000), 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 (<=10000) 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

题目大意

给出情侣名单，再给出聚会名单，聚会时没有对象或者对象不在场的都是可怜人，输出人数和人员名单，按id顺序输出。

解题报告

用一个map记录清理名单，在看聚会时，如果对象不在聚会单身名单里，自己就是单身，加入名单，如果对象在，就把对象从名单中剔除。 注意，如果想要有结尾换行，在没有人员单身时注意不要有多余换行。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/*
* Problem: 1121. Damn Single (25)
* Author: HQ
* Time: 2018-03-11
* State: Done
* Memo: set、map的应用
*/
#include "iostream"
#include "set"
#include "map"
#include "string"
using namespace std;

map<string,string> couple;
set<string> single;
int N,M;


int main() {
    cin >> N;
    string x,y;
    for (int i = 0; i < N; i++) {
        cin >> x>>y;
        couple[x] = y;
        couple[y] = x;
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> x;
        if (single.find(couple[x]) != single.end())
            single.erase(single.find(couple[x]));
        else
            single.insert(x);
    }
    cout << single.size() << endl;
    bool first = true;
    for (set<string>::iterator it = single.begin(); it != single.end(); it++) {
        if (first) {
            cout << *it;
            first = false;
        }
        else
            cout << " " << *it;
    }
    system("pause");
}