"单身狗" 是中文对于单身人士的一种爱称. 本题请你从上万人的大型派对中找出落单的客人, 以便给予特殊关爱.
输入格式:
输入第一行给出一个正整数 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
时间复杂度:$O(N * logN)$
代码:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 1e5 + 10;
- int a[10010], vis[maxn], out[10010];
- int main() {
- int N;
- scanf("%d", &N);
- map<int, int> mp;
- mp.clear();
- for(int i = 1; i <= N; i ++) {
- int x, y;
- scanf("%d%d", &x, &y);
- mp[x] = y;
- mp[y] = x;
- }
- int M;
- scanf("%d", &M);
- memset(vis, 0, sizeof(vis));
- for(int i = 1; i <= M; i ++) {
- scanf("%d", &a[i]);
- vis[a[i]] = 1;
- }
- int num = 0;
- bool flag = false;
- for(int i = 1; i <= M; i ++) {
- if(vis[mp[a[i]]] == 0) {
- num ++;
- out[num] = a[i];
- }
- }
- sort(out + 1, out + num + 1);
- printf("%d\n", num);
- for(int i = 1; i <= num; i ++) {
- printf("%05d", out[i]);
- printf("%s", i != num ? "":"\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2769593.html