PAT_1121

1121 Damn Single

题目描述

“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:

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

Sample Output:

1
2
5
10000 23333 44444 55555 88888

思路

题目中给出n对夫妇,然后给出m个来聚会的人,找出来聚会中单身的人,如果情侣没有来,那么也算单身

可以使用map存储上面的夫妇信息,也可以直接使用数组进行保存, 然后再来聚会的人中,依次遍历,如果不存在伴侣则直接保存到另一个vector中,否则判断自己的情侣有没有来

程序

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <cmath>
#include <map>
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 100000;
typedef long long ll;
int couple[maxn],x;
bool come[maxn];
vector<int> ans,wait;


int main()
{
fill(couple,couple+maxn,-1);
int n,m,a,b;
scanf("%d",&n);
for(int i = 0;i < n;i ++)
{
scanf("%d%d",&a,&b);
couple[a] = b;couple[b] = a;
}
scanf("%d",&m);
for(int i =0 ;i < m;i ++)
{
scanf("%d",&x);
if(couple[x] == -1)
ans.push_back(x);
else
wait.push_back(x),come[x] = 1;
}
for(int i = 0;i < wait.size();i ++)
if(!come[couple[wait[i]]])
ans.push_back(wait[i]);
sort(ans.begin(),ans.end());

printf("%d\n",ans.size());
for(int i = 0;i < ans.size();i ++)
printf("%05d%c",ans[i],i==ans.size()-1?'\n':' ');

return 0;
}
-------------本文结束感谢您的阅读-------------
显示 Gitment 评论