1. 题目

PAT (Basic Level) Practice (中文): 1065

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

1.1. 输入格式:

输入第一行给出一个正整数 N(≤ 50 000),是已知夫妻/伴侣的对数;随后 N 行,每行给出一对夫妻/伴侣——为方便起见,每人对应一个 ID 号,为 5 位数字(从 00000 到 99999),ID 间以空格分隔;之后给出一个正整数 M(≤ 10 000),为参加派对的总人数;随后一行给出这 M 位客人的 ID,以空格分隔。题目保证无人重婚或脚踩两条船。

1.2. 输出格式:

首先第一行输出落单客人的总人数;随后第二行按 ID 递增顺序列出落单的客人。ID 间用 1 个空格分隔,行的首尾不得有多余空格。

1.3. 输入样例:

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

1.4. 输出样例:

5
10000 23333 44444 55555 88888

2. 作答

2.1. 思路解析

需要注意的是:这道题在最后输出客人ID时,需要在不足5位的ID号前补0。
我的方法:为所有单身客人匹配一个绝对不会出席的“虚假伴侣public”,然后再使用循环,查找出席的客人中谁的伴侣不出席则列为“单身狗”。

2.2. 代码

#include "stdio.h"

struct Couple {
    int attend;
    struct Couple *next;
}couple[100000], public;

int main(int argc, char const *argv[]) {
    int n, i, m1, m2, tmp, tot, flag=1;
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d%d", &m1, &m2);
        couple[m1].next = &couple[m2];
        couple[m2].next = &couple[m1];
    }
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d", &tmp);
        couple[tmp].attend = 1;
        if (!couple[tmp].next) couple[tmp].next = &public;
    }
    public.attend = 0;
    tot = n;

    for (i = 0; i < 100000; ++i) {
        if (couple[i].attend && couple[i].next->attend == 1) {
            --tot;
        }
    }
    printf("%d\n", tot);
    for (i = 0; i < 100000; ++i) {
        if (couple[i].attend && couple[i].next->attend == 0) {
            printf("%s%05d", flag?"":" ", i);
            flag = 0;
        }
    }
    return 0;
}

2.3. 评测结果

提交时间 状态 分数 题目 编译器 耗时 用户
2019/3/3 02:04:40 答案正确 25 1065 C (gcc) 24 ms soulans
测试点 结果 耗时 内存
0 答案正确 2 ms 384 KB
1 答案正确 2 ms 256 KB
2 答案正确 2 ms 256 KB
3 答案正确 24 ms 1792 KB
4 答案正确 23 ms 1920 KB