1065 单身狗 (25分)
一、题干
“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。
输入格式：
输入第一行给出一个正整数 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 <iostream>
#include <iomanip>
#include<string>
#include<algorithm>
using namespace std;
int main() {
int N;
cin >> N;
int dog[100000] = { -1 };//不能初始化为0，测试点1有样例是00000
for (int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
dog[a] = b;
dog[b] = a;
}
int M , may[10010];
cin >> M;
for (int i = 0; i < M; i++) {
cin >> may[i];
}
sort(may, may + M);
int count = 0, rdog[10010];
for (int i = 0; i < M; i++) {
int flag = 0;
if (dog[may[i]]!=-1) {
for (int j = 0; j < M; j++) {
if (may[j] == dog[may[i]]) flag = 1;
}
if (flag == 1) {
continue;
}
}
rdog[count++] = may[i];
}
cout << count << endl;
for (int i = 0; i < count; i++) {
if (i!= count-1) {
cout << setfill('0')<<setw(5)<<rdog[i] << " ";//五位数补零
}
else {
cout << setfill('0') << setw(5)<<rdog[i];
}
}
return 0;
}
三、思路
思路
寻找另一半所否在party中，可以创立一个数组，在读取数据时直接将另一半序号读入到对应的数组序号中，这是为了方便查找，测试点4，5就是考察时间效率的问题，本题要以空间换时间。此外要注意的是，在初始化数组时，不能初始化为0，因为在测试点1中的数据就有00001。最后在测试点3考察了补零的情况。
