Keshawn_lu's Blog

PAT 1065.单身狗

字数统计: 585阅读时长: 2 min
2021/02/20 Share

题目简介:

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

输入格式:

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

输出格式:

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

输入样例:

1
2
3
4
5
6
3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

输出样例:

1
2
5
10000 23333 44444 55555 88888

思路:

首先将夫妻关系存入哈希表。

对于参与派对的人来说,如果其本身就没有夫妻关系,则直接加入单身狗数组中,否则做个标记,代表他来派对了。

然后再遍历这些有夫妻关系并且来派对的人,通过哈希表来判断其伴侣是否来了派对,若没有则加入单身狗数组。

单身狗数组用set存储,可自动帮我们进行排序。

tip:

  • 注意set的遍历方法

代码如下:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <set>

using namespace std;


int main()
{
int N;
cin >> N;

unordered_map<string, string> map;
for (int i = 0; i < N; i++) {

string man, woman;
cin >> man >> woman;

map[man] = woman;
map[woman] = man;
}

int M;
cin >> M;

set<string> single;
unordered_map<string, int> exist;
vector<string> people;
for (int i = 0; i < M; i++) {

string person;
cin >> person;

if (map[person] != "") {

exist[person] = 1;
people.push_back(person);
}
else
single.insert(person); //本身就无对象
}

for (int i = 0; i < people.size(); i++) {


if (!exist[map[people[i]]])
single.insert(people[i]);
}

cout << single.size() << endl;

for (set<string>::iterator it = single.begin(); it != single.end(); it++) {

if (it != single.begin())
cout << " ";

cout << *it;
}
}
CATALOG
  1. 1. 题目简介:
    1. 1.1. 输入格式:
    2. 1.2. 输出格式:
    3. 1.3. 输入样例:
    4. 1.4. 输出样例:
  2. 2. 思路:
  3. 3. 代码如下: