由于这道题在留的作业中，排序和查找都有，所以我先写这道题（图的先放放）
“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。
输入格式：
输入第一行给出一个正整数 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！！
（很有意义的一道题）
