一、题目描述

原题链接 “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 (≤ 50,000), 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 (≤ 10,000) 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

二、解题思路

题目还是比较简单的，可以用一个比较大的数组存放每个人对应的伴侣，如果没有则设为-1，用一个bool数组来标记来到party的人。将伴侣不在或者没有伴侣的人存放进结果数组，最后排序输出即可。

三、AC代码

#include<iostream> #include<cstdio> #include<algorithm> #include<vector> using namespace std; const int maxn = 100010; int pairs[maxn]; //记录每个人的“另一半”，-1表示没有 bool isHere[maxn] = {false}; //标记每个人是否在party中 vector<int> all, ans; int main() { int N, tmp1, tmp2, num; fill(pairs, pairs+maxn, -1); scanf("%d", &N); for(int i=0; i<N; i++) { scanf("%d%d", &tmp1, &tmp2); pairs[tmp1] = tmp2; pairs[tmp2] = tmp1; } scanf("%d", &num); for(int i=0; i<num; i++) { scanf("%d", &tmp1); isHere[tmp1] = true; all.push_back(tmp1); } for(int i=0; i<all.size(); i++) { if(pairs[all[i]] < 0 || !isHere[pairs[all[i]]]) ans.push_back(all[i]); //没有“另一半”或者“另一半”不在这里，存入结果数组 } sort(ans.begin(), ans.end()); printf("%d\n", ans.size()); for(int i=0; i<ans.size(); i++) { if(i==0) printf("%05d", ans[i]); else printf(" %05d", ans[i]); } }