傳送門
https://pintia.cn/problem-sets/994805260223102976/problems/994805266942377984
題目
“單身狗”是中文對(duì)于單身人士的一種愛稱偿曙。本題請(qǐng)你從上萬(wàn)人的大型派對(duì)中找出落單的客人单料，以便給予特殊關(guān)愛拌汇。
輸入格式：
輸入第一行給出一個(gè)正整數(shù)N（<=50000），是已知夫妻/伴侶的對(duì)數(shù)；隨后N行兵扬，每行給出一對(duì)夫妻/伴侶——為方便起見酸休，每人對(duì)應(yīng)一個(gè)ID號(hào)，為5位數(shù)字（從00000到99999）洋访，ID間以空格分隔镣陕；之后給出一個(gè)正整數(shù)M（<=10000），為參加派對(duì)的總?cè)藬?shù)姻政；隨后一行給出這M位客人的ID呆抑，以空格分隔。題目保證無(wú)人重婚或腳踩兩條船汁展。
輸出格式：
首先第一行輸出落單客人的總?cè)藬?shù)鹊碍；隨后第二行按ID遞增順序列出落單的客人厌殉。ID間用1個(gè)空格分隔，行的首尾不得有多余空格侈咕。
輸入樣例：
3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333
輸出樣例：
5
10000 23333 44444 55555 88888
分析
真是一道惡趣味的題公罕，不過作為最后一道，難度倒是不大耀销。
1.建立一個(gè)伴侶表楼眷，用每個(gè)人ID作為索引，在其索引下熊尉，存放夫妻/伴侶的ID罐柳；
舉例來(lái)講，若11111和22222互為伴侶狰住，則table[11111]=22222张吉，table[22222]=11111。
2.先把所有參加排隊(duì)的賓客ID存到數(shù)組里面催植；
3.遍歷賓客數(shù)組肮蛹，查找對(duì)應(yīng)伴侶表里面的伴侶是否能在賓客的數(shù)組找到，如果找不到创南，說明是單身狗蔗崎，將其加入到單身狗的數(shù)組里面；
4.遍歷賓客數(shù)組完成后扰藕，對(duì)單身狗數(shù)組排序（升序）缓苛；
5.遍歷輸出單身狗數(shù)組。
注意：ID不足五位的邓深，要用0補(bǔ)位未桥，就這一個(gè)坑。
對(duì)了芥备，還有冬耿，末尾不要輸出一個(gè)換行符，容易有錯(cuò)萌壳。
強(qiáng)迫癥是病亦镶，得治。
源代碼
//C/C++實(shí)現(xiàn)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int table[100000];
int main(){
int n;
scanf("%d", &n);
int a, b;
for(int i = 0; i < n; ++i){
scanf("%d %d", &a, &b);
//建立相互映射關(guān)系
table[a] = b;
table[b] = a;
}
scanf("%d", &n);
vector<int> v(n);
vector<int> doge;
for(int i = 0; i < n; ++i){
scanf("%d", &v[i]);
}
for(int i = 0; i < n; ++i){
vector<int>::iterator result = find(v.begin(), v.end(), table[v[i]]);
if(result == v.end()){ //說明沒找到他/她的伴侶
doge.push_back(v[i]); //單身狗的隊(duì)伍又壯大了
}
}
sort(doge.begin(),doge.end());
printf("%d\n", doge.size());
for(int i = 0; i < doge.size(); ++i){
if(i == 0){
printf("%05d", doge[i]);
}
else{
printf(" %05d", doge[i]);
}
}
// printf("\n");
}
