傳送門

https://pintia.cn/problem-sets/994805260223102976/problems/994805266942377984

題目

“單身狗”是中文對(duì)于單身人士的一種愛(ài)稱。本題請(qǐng)你從上萬(wàn)人的大型派對(duì)中找出落單的客人，以便給予特殊關(guān)愛(ài)。
輸入格式：
輸入第一行給出一個(gè)正整數(shù)N（<=50000），是已知夫妻/伴侶的對(duì)數(shù)；隨后N行，每行給出一對(duì)夫妻/伴侶——為方便起見(jiàn)，每人對(duì)應(yīng)一個(gè)ID號(hào)，為5位數(shù)字（從00000到99999），ID間以空格分隔；之后給出一個(gè)正整數(shù)M（<=10000），為參加派對(duì)的總?cè)藬?shù)；隨后一行給出這M位客人的ID，以空格分隔。題目保證無(wú)人重婚或腳踩兩條船。
輸出格式：
首先第一行輸出落單客人的總?cè)藬?shù)；隨后第二行按ID遞增順序列出落單的客人。ID間用1個(gè)空格分隔，行的首尾不得有多余空格。
輸入樣例：
3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333
輸出樣例：
5
10000 23333 44444 55555 88888

分析

真是一道惡趣味的題，不過(guò)作為最后一道，難度倒是不大。
1.建立一個(gè)伴侶表，用每個(gè)人ID作為索引，在其索引下，存放夫妻/伴侶的ID；
舉例來(lái)講，若11111和22222互為伴侶，則table[11111]=22222，table[22222]=11111。
2.先把所有參加排隊(duì)的賓客ID存到數(shù)組里面；
3.遍歷賓客數(shù)組，查找對(duì)應(yīng)伴侶表里面的伴侶是否能在賓客的數(shù)組找到，如果找不到，說(shuō)明是單身狗，將其加入到單身狗的數(shù)組里面；
4.遍歷賓客數(shù)組完成后，對(duì)單身狗數(shù)組排序（升序）；
5.遍歷輸出單身狗數(shù)組。

注意：ID不足五位的，要用0補(bǔ)位，就這一個(gè)坑。

對(duì)了，還有，末尾不要輸出一個(gè)換行符，容易有錯(cuò)。
強(qiáng)迫癥是病，得治。

源代碼

//C/C++實(shí)現(xiàn)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int table[100000];

int main(){
    int n;
    scanf("%d", &n);
    int a, b;
    for(int i = 0; i < n; ++i){
        scanf("%d %d", &a, &b);
        //建立相互映射關(guān)系 
        table[a] = b;
        table[b] = a;
    }
    scanf("%d", &n);
    vector<int> v(n);
    vector<int> doge;
    for(int i = 0; i < n; ++i){
        scanf("%d", &v[i]);
    }
    for(int i = 0; i < n; ++i){
        vector<int>::iterator result = find(v.begin(), v.end(), table[v[i]]);
        if(result == v.end()){ //說(shuō)明沒(méi)找到他/她的伴侶 
            doge.push_back(v[i]); //單身狗的隊(duì)伍又壯大了 
        }
    }
    sort(doge.begin(),doge.end());
    printf("%d\n", doge.size());
    for(int i = 0; i < doge.size(); ++i){
        if(i == 0){
            printf("%05d", doge[i]);
        }       
        else{
            printf(" %05d", doge[i]);
        }
    }
//  printf("\n");
}