当前位置: 代码迷 >> 综合 >> PAT 1065.单身狗
  详细解决方案

PAT 1065.单身狗

热度:112   发布时间:2023-11-17 23:10:02.0

题目:

输入格式:

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

输出格式:

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


测试点3:因为五位数字!!!如果输入小于五位数的数字会去掉前面的0再存 所以输出的时候要控制格式 往前补0


思路:先配对了 一个标记情侣数组

#include<iostream>
#include<vector>
using namespace std;
#include<algorithm>
int cmp(int a,int b)
{return a<b;
}int main()
{int book[100005]={-1},list[100005]={0},guest[100005]={0};int n,i,j,men,women;cin >> n;for(i=0;i<n;i++){cin >> men >> women;book[men] = women;book[women] = men;}int a[100005],count=0;int m;cin >> m;for(i=0;i<m;i++){cin >> guest[i];if(book[guest[i]]!=-1)//有伴侣 list[book[guest[i]]] = 1;//名单上伴侣的名字 }for(i=0;i<m;i++){if(!list[guest[i]])a[count++] = guest[i];}sort(a,a+count,cmp);cout << count << endl;if(count != 0){ for(i=0;i<count-1;i++)printf("%05d ",a[i]); printf("%05d",a[i]);cout << endl;}
}

将男女的下标对应的值存对方的下标


输入人数之后遍历判断


如果这个人有伴侣 就把伴侣加到名单上去(如果伴侣也来了 自己也会被加入)


最后遍历一遍判断不在名单上的全部排序输出


完整code