【PAT乙級】單身狗

2019 年 11 月 8 日
筆記

本文鏈接：https://blog.csdn.net/weixin_42449444/article/details/89193454

題目描述：

「單身狗」是中文對於單身人士的一種愛稱。本題請你從上萬人的大型派對中找出落單的客人，以便給予特殊關愛。

輸入描述：

輸入第一行給出一個正整數 N（≤ 50 000），是已知夫妻/伴侶的對數；隨後 N 行，每行給出一對夫妻/伴侶——為方便起見，每人對應一個 ID 號，為 5 位數字（從 00000 到 99999），ID 間以空格分隔；之後給出一個正整數 M（≤ 10 000），為參加派對的總人數；隨後一行給出這 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

解題思路：

建立一個map，其中map的key和value存放的字符串是一對夫妻/伴侶的ID。再建立一個set用來存放參加派對的人的ID，當參加派對的人沒有對象，或者他的對象沒有出現在set中時，就說明這是個落單客人，把所有落單的客人都放入一個叫ans的vector中。ans.size()就是落單客人的總人數，直接無腦for-each輸出ans中的所有元素即可。

AC代碼：

#include <bits/stdc++.h>  using namespace std;    int main()  {      int N;   //已知夫妻/伴侶的對數      cin >> N;      map<string,string> m;  //map的value存放的是key的夫妻/伴侶      for(int i = 0; i < N; i++)      {          string A,B;          cin >> A >> B;          m[A] = B;          m[B] = A;      }      int M;   //需要參加派對的人數      cin >> M;      set<string> s;   //set用來記錄參加派對的人的ID      for(int i = 0; i < M; i++)      {          string temp;          cin >> temp;          s.insert(temp);      }      vector<string> ans;   //一個存放着落單的客人ID的名單      for(auto it : s)      {          if(s.count(m[it]) == 0)          {              ans.push_back(it);   //把落單的客人放入名單          }      }      cout << ans.size() << endl;   //輸出落單客人的總人數      bool isVirgin = true;   //判斷是不是第一次      for(auto it : ans)      {          if(isVirgin)          {              cout << it;              isVirgin = false;          }          else          {              cout << " " << it;          }      }      return 0;  }

———————————————2019.07.17更新——————————————————

HBU訓練營有出現這道題，我感覺我這次寫的代碼比之前刷PAT乙級時寫的要更加簡潔。

AC代碼：

#include <bits/stdc++.h>  using namespace std;    int main()  {      int N;   //已知戀愛狗對數      cin >> N;      map<int,int> m;   //用來存戀愛狗信息,key是本人,value是對象      for(int i = 0; i < N; i++)      {          int id1,id2;          cin >> id1 >> id2;          m[id1] = id2;          m[id2] = id1;      }      int M;    //參加派對的總人數      cin >> M;      vector<int> v;   //用來存參加派對的人的信息      for(int i = 0; i < M; i++)      {          int id;          cin >> id;          v.push_back(id);      }      vector<int> ans;   //落單者的信息      for(auto it : v)      {          if(find(v.begin(),v.end(),m[it]) == v.end())   //落單的話          {              ans.push_back(it);          }      }      sort(ans.begin(),ans.end());   //升序排列      printf("%dn",ans.size());      for(int i = 0; i < ans.size(); i++)      {          printf("%s%05d",(i?" ":""),ans[i]);    //i!=0前置輸出空格      }      return 0;  }