PAT乙级1065 单身狗 (25分)

r囧r小猫 2023-03-13 06:17 9阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
1.couple【i】存储 i的夫妻id，-1表示不存在夫妻/伴侣；hash【i】为1表示 i出席派对  
2.result存储落单的客人，judge存储那些还需进一步判别的人  
3.读入参加派对的每个人的时候，如果他不存在伴侣（即couple【他】==-1），直接放入result，否则放入judge  
4.遍历judge数组中的每个人，如果他的伴侣不在派对中（hash\[couple\[ judge\[ i \] \] \]==0），放入result数组  
5.最后按照格式输出result中的id即可，注意id是5位数，需要前补0

#include<iostream>
    #include<cstdio>
    #include<vector>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int main()
    { 
      int n,k,temp;
      int couple[100005];//存储每个人的夫妻
      memset(couple,-1,sizeof(couple));
      cin>>n;
      for(int i=0;i<n;i++)
      { 
        int a,b;
        scanf("%d%d",&a,&b);
        couple[a]=b;
        couple[b]=a;
      }
      scanf("%d",&k);
      int hash[100005];
      vector<int> v(k),result,judge;
      memset(hash,0,sizeof(hash));
      for(int i=0;i<k;i++)
      { 
        scanf("%d",&v[i]);
        hash[v[i]]=1;
        if(couple[v[i]]!=-1)//存在夫妻
        { 
          judge.push_back(v[i]);
        }
        else result.push_back(v[i]);
      }
      for(int i=0;i<judge.size();i++)
      { 
        if(hash[couple[judge[i]]]==0)result.push_back(judge[i]);
      }
      sort(result.begin(),result.end());
      cout<<result.size()<<endl;
      if(result.size()!=0)
      { 
      	printf("%05d",result[0]);
      	for(int i=1;i<result.size();i++)
      	printf(" %05d",result[i]);
      	cout<<endl;
      }
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230312/8e1b1996e3b8459fb503b26898818506.png