PAT Basic 1065. 单身狗

1. 题目描述：

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

2. 输入格式：

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

3. 输出格式：

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

4. 输入样例：

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

5. 输出样例：

5
10000 23333 44444 55555 88888

6. 性能要求：

Code Size Limit
16 KB
Time Limit
200 ms
Memory Limit
64 MB

思路：

准除草题，这里只有一对夫妻/伴侣同时参加派对才不会变成单身狗。。。定义int型数组coupleRec记录couple关系，然后对每一个参加派对的客人，判断其是否存在couple关系并且couple同时参加了派对，两个条件都满足的话从单身狗中删去。

第一次提交时testpoint1报wrong answer，排查后发现忽略了ID为0的情况。这里判断couple是否同时参加了派对使用的是遍历判断，相当于两个嵌套循环，一开始以为会超时，但是没有。。。不过这种方法确实有点丑陋。参考大佬的题解：1065. 单身狗(25)-PAT乙级真题_柳婼的博客-CSDN博客，她是当将每个客人对象的标志置1，代表客人对象的对象（即客人自己）参加了派对，是比较巧妙的思路。

My Code:

#include <stdio.h>
#include <stdlib.h> // malloc header, qsort header

int cmp(const void *num1, const void *num2);

// first submit testpoint1 wrong answer
int main(void)
{
    int coupleRec[100000] = {0};
    int cpCount = 0;
    int cp1=0, cp2=0;
    int i=0; // iterator
    int partyCount = 0;
    int *pParty = NULL;
    int j=0; // iterator
    int dogCount = 0;
    int firstBlood = 0;
    
    // fixed testpoint1, need to consider 00000
    for(i=0; i<100000; ++i)
    {
        coupleRec[i] = -1;
    }
    
    scanf("%d", &cpCount);
    for(i=0; i<cpCount; ++i)
    {
        scanf("%d%d", &cp1, &cp2);
        coupleRec[cp1] = cp2;
        coupleRec[cp2] = cp1;
    }
    
    scanf("%d", &partyCount);
    dogCount = partyCount;
    pParty = (int *)malloc(sizeof(int) * partyCount);
    for(i=0; i<partyCount; ++i)
    {
        scanf("%d", pParty+i);
    }
    
    for(i=0; i<partyCount; ++i)
    {
        if(pParty[i]>=0 && coupleRec[pParty[i]]>=0) // have couple record
        {
            for(j=0; j<partyCount; ++j)
            {
                if(coupleRec[pParty[i]] == pParty[j]) // couple both join the party
                {
                    pParty[i] = -1;
                    pParty[j] = -1;
                    dogCount -= 2;
                    break;
                }
            }
        }
    }
    
    printf("%d\n", dogCount);
    qsort(pParty, partyCount, sizeof(int), cmp);
    for(i=0; i<partyCount; ++i)
    {
        if(pParty[i]>=0)
        {
            if(firstBlood)
            {
                printf(" %05d", pParty[i]);
            }
            else
            {
                firstBlood = 1;
                printf("%05d", pParty[i]);
            }
        }
    }
    // omit this if statement will cause prensentation error when dogCount == 0.
    if(firstBlood) // this new line in the end is not necessary.
        printf("\n");
    
    free(pParty);
    return 0;
}

int cmp(const void *num1, const void *num2)
{
    return (*(int *)num1 - *(int *)num2);
}