“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。
输入第一行给出一个正整数 N(≤?50 000),是已知夫妻/伴侣的对数;随后 N 行,每行给出一对夫妻/伴侣——为方便起见,每人对应一个 ID 号,为 5 位数字(从 00000 到 99999),ID 间以空格分隔;之后给出一个正整数 M(≤?10 000),为参加派对的总人数;随后一行给出这 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
?下面是我的代码:
#include <bits/stdc++.h> //万能头文件
using namespace std;
int main(){
map<string,string>love; //将情侣配对标记
map<string,bool>islove; //将有对象的人标记
vector<string> total; //存放所有有对象的人,用于后续遍历判断
vector<string> ans; //存放答案
int n; cin >> n;
string a,b;
while(n--) {
cin >> a >> b;
love[a] = b; //标记情侣(使得后续通过a可以找到b,通过b也能找到a)
love[b] = a;
islove[a] = true; //标记已经有对象的人,用于后续筛选出无对象的人
islove[b] = true;
}
int k; cin >> k;
string s;
for (int i = 0; i < k; i++) {
cin >> s;
if (!islove[s]) {
ans.push_back(s); //无标记的人直接进入答案数组
}
else {
total.push_back(s); //有标记的进入total数组,后续筛选
if (islove[love[s]] == true) { //重点:判断对象,如果对象是true,说 明对象还没来,先把此人标记改为false;
islove[s] = false;
}else if (islove[love[s]] == false) { //如果对象为false,说明对象已经来了,再把对象改回true,因此后续遍历total数组,所有false的人就代表落单的,即对象没来的
islove[love[s]] = true;
}
}
}
for (int i = 0; i < total.size(); i++) { //遍历,将false的人存入答案数组
if (islove[total[i]] == false) {
ans.push_back(total[i]);
}
}
cout << ans.size() << endl; //输出第一个数据,即答案数组的个数
sort(ans.begin(),ans.end()); //照题目意思,从小到大排序
for (int i = 0; i < ans.size(); i++) { //最后输出答案,注意排版
if (i == 0) {cout << ans[i];}
else {cout << " " << ans[i];}
}
}