目录
目录题目
“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。
输入格式：
输入第一行给出一个正整数 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
代码
第一次错误尝试
思路
1.用数组a存储n队夫妻的id号
2.根据M位客人的id号遍历夫妻数组a，寻找落单
3.用数组l存储落单id，排序后输出
代码
#include<stdio.h>
void sort( int a[], int n );
int main()
{
int n;
int a[100];
scanf("%d",&n);
for(int i=0;i<2*n;i++)
scanf("%d",&a[i]);
int m;
scanf("%d",&m);
int l[100]={0};
int k=0;
for(int i=0;i<m;i++)
{
int id;
scanf("%d",&id);
int flag=0;//单身0
for(int j=0;j<2*n;j++)
{
if(id==a[j])
{
flag=1;
break;
}
}
if(flag==0)
{
l[k++]=id;
}
}
sort(l,k);
printf("%d\n",k);
for(int i=0;i<k-1;i++)
printf("%d ",l[i]);
printf("%d\n",l[k-1]);
return 0;
}
void sort( int a[], int n )
{
int k;//最小值下标
for(int i=0;i<n-1;i++)//第一个未排序元素的下标
{
k=i;
for(int j=i+1;j<n;j++)//在未排序元素中遍历找出最小值
{
if(a[k]>a[j])
{
k=j;
}
}
//已找到未排序元素中的最小值a[k]
//和第一个未排序的元素交换位置
if(k!=i)
{
int min=a[k];
a[k]=a[i];
a[i]=min;
}
}
}
运行结果
错误分析
误会了题意，题目要求找出在舞会上落单的人，即此人即使有伴侣，但是其伴侣不在舞会上，则此人也算落单。
第二次错误尝试
思路
1.用数组a存储n队夫妻的id号
2.用数组w存储m位客人
3.遍历数组w判断数组a中的任意夫妻是否都在排队上，若都在，则这对夫妻没有落单
4.将没有落单的夫妻从数组w中去掉，剩下的就是落单的客人。
代码
#include<stdio.h>
void sort( int a[], int n );
int xzld(int a[],int n,int w[],int m);
int main()
{
int n;
int a[100];
scanf("%d",&n);
for(int i=0;i<2*n;i++)
scanf("%d",&a[i]);
int m;
scanf("%d",&m);
int w[100];
for(int i=0;i<m;i++)
scanf("%d",&w[i]);
int k=xzld(a,n,w,m);
sort(w,k);
printf("%d\n",k);
for(int i=0;i<k-1;i++)
printf("%d ",w[i]);
printf("%d\n",w[k-1]);
return 0;
}
void sort( int a[], int n )
{
int k;//最小值下标
for(int i=0;i<n-1;i++)//第一个未排序元素的下标
{
k=i;
for(int j=i+1;j<n;j++)//在未排序元素中遍历找出最小值
{
if(a[k]>a[j])
{
k=j;
}
}
//已找到未排序元素中的最小值a[k]
//和第一个未排序的元素交换位置
if(k!=i)
{
int min=a[k];
a[k]=a[i];
a[i]=min;
}
}
}
int xzld(int a[],int n,int w[],int m)
{
int ld=m;
for(int i=0;i<2*n;i+=2)
{
int f1=-1,f2=-1;
for(int j=0;j<m;j++)
{
if(a[i]==w[j])
f1=j;
if(a[i+1]==w[j])
f2=j;
}
if(f1!=-1&&f2!=-1)//夫妻都在
{
for(int d=f1;d<ld-1;d++)
w[d]=w[d+1];
ld--;
for(int d=f2;d<ld-1;d++)
w[d]=w[d+1];
ld--;
}
}
return ld;
}
运行结果
错误分析
1.运行超时，2.id取上下界，无人单身
看了别人的思路：
用 -1 当初始值，均为单身狗（因为有 0 号客人，所以最好不用 0 当初始值）
用数组映射一对伴侣
用 -2 表示客人到场。读取客人入场，用映射寻找自己的伴侣，当自己单身或伴侣还未到场，自己-用 -2 表示到场
若映射的伴侣状态为 -2 到场，则两人配对成功，两人用 -3 表示脱离单身狗标签，单身狗数目减二
下次再想想。
标签：落单,单身,int,数组,伴侣,客人 From： https://www.cnblogs.com/wa2211lq/p/17827840.html