Chen

PAT-B 1065. 单身狗
“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。输入格式:输...
扫描右侧二维码阅读全文
13
2019/03

PAT-B 1065. 单身狗

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

输入格式:

输入第一行给出一个正整数N(<=50000),是已知夫妻/伴侣的对数;随后N行,每行给出一对夫妻/伴侣——为方便起见,每人对应一个ID号,为5位数字(从00000到99999),ID间以空格分隔;之后给出一个正整数M(<=10000),为参加派对的总人数;随后一行给出这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 8888

思路分析:
哈希表的应用,利用数组下标表示客人ID。
代码:

#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
int couple[MAX];      //保存不是单身的人,元素为对象ID
int guest[MAX] = {0}; //保存客人,下标为客人ID,元素值为1用于标记
int ans[MAX] = {0};
int main()
{
    //freopen("test.in", "r", stdin);
    int M, N;
    for (int i = 0; i < MAX; i++)
        couple[i] = -1;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int a, b;
        cin >> a >> b;
        couple[a] = b;
        couple[b] = a; //数组下标表示客人ID,元素值表示其对象的ID
    }
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        int t;
        cin >> t;
        guest[t] = 1; //下标表示客人ID,值为1表示该客人来了,为0表示没来
    }
    int j = 0, cnt = 0;
    for (int i = 0; i < MAX; i++)
    {
        if (guest[i] == 1 && guest[couple[i]] != 1)
        {
            cnt++;
            ans[j] = i;
            j++;
        }
    }
    cout << cnt << endl;
    if (cnt)
    {
        for (int i = 0; i < cnt; i++)
        {
            printf("%05d%c", ans[i], " \n"[i == cnt - 1]);
        }
    }
    return 0;
}
Last modification:May 11th, 2019 at 04:05 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment