7-1 单身狗(PTA - 数据结构)

?由于这道题在留的作业中，排序和查找都有，所以我先写这道题（图的先放放）

---

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

输入格式：

输入第一行给出一个正整数 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 88888

代码长度限制????????16 KB

时间限制????????????????200 ms

内存限制????????????????64 MB

---

?提交结果：

---

思路分析：?

? ? ? ? 要找，要排，限制了时间。

? ? ? ? 排序的话，这里使用了快速排序算法（真的很快！），其他有人用的堆排序，可以去尝试一下。找就得自己想办法找了。

如何输入：

? ? ? ? 题目中给的是一对一对的，所以这里考虑要整个结构体去存：

typedef struct {
    int his_couple;    //他的对象
    int BOrS;          //对象比他大还是小，小的话是-1，大的话是1
    int yeah;          //有对象，1为有，0为无，2为查找的时候已经找到过他对象了
}Couple;

? ? ? ? ?下标当作id来存一个人的信息。

如何查找（顺便找到单身人数）：

? ? ? ? 先排序一下输入的人的id，小的在前面。然后开始遍历来的人，也就是数组man。如果一个人在couple中的yeah值为1，而且BOrS（big or small）为1，那么就去往后找他的对象来没来，没来就进入单身行列，来了就不是。如果BOrS为-1（因为是从前往后，从小往大id找对象的，他要是被找过，那只能说他对象比他小，且yeah已经被置为了2），那么检查他的yeah，yeah不是2就进入单身行列。其余yeah都是0，那只能也进入单身行列。

int Search(Couple c[],int man[], int nums,int single[]){
    int flag = 0;
    for (int i = 0;i<nums;i++) {
        if (c[man[i]].yeah == 1) {
            if (c[man[i]].BOrS == 1) {
                int judge = 0;
                for (int j = i + 1; j < nums; ++j) {
                    if (c[man[j]].his_couple == man[i]) {   //有他伴侣
                        c[man[j]].yeah = 2;         //已经检查过了
                        judge = 1;
                        break;
                    }
                }
                if(judge == 0)
                    single[flag++] = man[i];
            }
            if ((c[man[i]].BOrS == -1)&&(c[man[i]].yeah != 2)) {
                single[flag++] = man[i];
            }
        }
        else if(c[man[i]].yeah == 2) {
            continue;
        }
        else {
            single[flag++] = man[i];
        }
    }
    return flag;
}

输出打印：

? ? ? ? 因为man已经排好序了，所以得到的single数组也应当是有序的，所以直接打印就行，然后注意一下空格和0补位。之前写过补位代码，直接拿过来。space处理空格问题（具体见主函数传参）。

void Print(int id,int space){
    if(id == -1)
        return;
    if(id>=10000)
        printf("%d",id);
    else if(id >= 1000)
        printf("0%d",id);
    else if(id >= 100)
        printf("00%d",id);
    else if(id >= 10){
        printf("000%d",id);
    }
    else if(id >= 0){
        printf("0000%d",id);
    }
    if(space == 1)
        printf(" ");
}

注意：?

? ? ? ? 一定要初始化结构体数组！！！

---

代码展示：?

//
// Created by DDD on 2023/12/19.
//
#include <stdio.h>
#include <malloc.h>
#define MAX 100000

typedef struct {
    int his_couple;
    int BOrS;
    int yeah;
}Couple;

void QuickSort(int array[], int low, int high) {    //快排
    int i = low;
    int j = high;
    if(i >= j) {
        return;
    }
    int temp = array[low];
    while(i != j) {
        while(array[j] >= temp && i < j) {
            j--;
        }
        while(array[i] <= temp && i < j) {
            i++;
        }
        if(i < j) {
            int t = array[j];
            array[j] = array[i];
            array[i] = t;

        }
    }
    int t = array[low];
    array[low] = array[i];
    array[i] = t;
    QuickSort(array, low, i - 1);
    QuickSort(array, i + 1, high);
}

int Search(Couple c[],int man[], int nums,int single[]){
    int flag = 0;
    for (int i = 0;i<nums;i++) {
        if (c[man[i]].yeah == 1) {
            if (c[man[i]].BOrS == 1) {
                int judge = 0;
                for (int j = i + 1; j < nums; ++j) {
                    if (c[man[j]].his_couple == man[i]) {   //有他伴侣
                        c[man[j]].yeah = 2;         //已经检查过了
                        judge = 1;
                        break;
                    }
                }
                if(judge == 0)
                    single[flag++] = man[i];
            }
            if ((c[man[i]].BOrS == -1)&&(c[man[i]].yeah != 2)) {
                single[flag++] = man[i];
            }
        }
        else if(c[man[i]].yeah == 2) {
            continue;
        }
        else {
            single[flag++] = man[i];
        }
    }
    return flag;
}

void Print(int id,int space){
    if(id == -1)
        return;
    if(id>=10000)
        printf("%d",id);
    else if(id >= 1000)
        printf("0%d",id);
    else if(id >= 100)
        printf("00%d",id);
    else if(id >= 10){
        printf("000%d",id);
    }
    else if(id >= 0){
        printf("0000%d",id);
    }
    if(space == 1)
        printf(" ");
}

int main(){
    int n;
    scanf("%d",&n);
    Couple c[MAX]={0};
    for (int i = 0; i < n; ++i) {
        int x, y;
        scanf("%d %d",&x,&y);
        c[x].his_couple = y;
        c[y].his_couple = x;
        c[x].yeah = 1;
        c[y].yeah = 1;          //有伴侣
        if(x>y){
            c[x].BOrS = -1;     //他的伴侣比他小
            c[y].BOrS = 1;
        }
        else{
            c[x].BOrS = 1;
            c[y].BOrS = -1;
        }
    }
    int m;
    scanf("%d",&m);
    int man[m];
    for (int i = 0; i < m; ++i) {
        scanf("%d",&man[i]);
    }
    int single[m];
    QuickSort(man,0,m-1);
    if(n!=0) {
        int flag = Search(c, man, m, single);
        printf("%d\n", flag);
        for (int i = 0; i < flag; ++i) {
            if (i < flag - 1)
                Print(single[i],1);
            else {
                Print(single[i],0);
            }
        }
    }
    else{
        printf("%d\n",m);
        for (int i = 0; i < m; ++i) {
            if (i < m - 1)
                Print(man[i],1);
            else {
                Print(man[i],0);
            }
        }
    }
}

---

return 0;//祝大家早日离开single，把自己的yeah置为1！！

（很有意义的一道题）