乐趣区

关于c++:PAT甲级1121-Damn-Single

题目粗心

有一个长度为 N 的 couple list,列表上每一行的人都互为情侣,当初有 M 集体来加入晚会,须要按程序给出没有伴侣的嘉宾

算法思路

应用一个 map 记录每一个人的 couple,对于输出的所有的客人,只有没有呈现在 couple 中,就阐明是独身,增加进 singles 数组中,如果呈现在了 couple 中然而其伴侣不在来访嘉宾中,阐明此人也是独身,增加进 singles 数组中,最初输入 singles 数组即可。

提交后果

AC 代码

#include<cstdio>
#include<unordered_map>
#include<set>
#include<vector>

using namespace std;

unordered_map<int,int> couples;

int main() {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        int a,b;
        scanf("%d %d",&a,&b);
        couples[a+1] = b+1;
        couples[b+1] = a+1;
    }
    int m;
    scanf("%d",&m);
    set<int> guests;
    for(int i=0;i<m;++i){
        int a;
        scanf("%d",&a);
        guests.insert(a+1);
    }
    vector<int> singles;
    for(auto it:guests){if(couples[it]==0){
            // 没有呈现在 couple list 上
            singles.push_back(it);
        }else if(guests.find(couples[it])==guests.end()){
            // 呈现在了 couple list 上,然而另外一半没有来
            singles.push_back(it);
        }
    }
    printf("%lu\n",singles.size());
    for(int i=0;i<singles.size();++i){printf("%05d",singles[i]-1);
        if(i<singles.size()-1){printf(" ");
        }
    }
    return 0;
}
退出移动版