乙级 1065 单身狗

发布时间:2024年01月03日

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

输入格式:

输入第一行给出一个正整数 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

?下面是我的代码:

#include <bits/stdc++.h>        //万能头文件
using namespace std;

int main(){
    map<string,string>love;            //将情侣配对标记
    map<string,bool>islove;            //将有对象的人标记
    
    vector<string> total;            //存放所有有对象的人,用于后续遍历判断
    vector<string> ans;            //存放答案
    
    int n;    cin >> n;
    string a,b;
    while(n--) {
        cin >> a >> b;
        love[a] = b;                //标记情侣(使得后续通过a可以找到b,通过b也能找到a)
        love[b] = a;
        islove[a] = true;            //标记已经有对象的人,用于后续筛选出无对象的人
        islove[b] = true;
    }
    
    int k;    cin >> k;
    string s;
    for (int i = 0; i < k; i++) {
        cin >> s;
        
        if (!islove[s]) {
            ans.push_back(s);                //无标记的人直接进入答案数组
        }
        else {
            total.push_back(s);                //有标记的进入total数组,后续筛选
            if (islove[love[s]] == true) {            //重点:判断对象,如果对象是true,说                                    明对象还没来,先把此人标记改为false;
                islove[s] = false;
            }else if (islove[love[s]] == false) {        //如果对象为false,说明对象已经来了,再把对象改回true,因此后续遍历total数组,所有false的人就代表落单的,即对象没来的
                islove[love[s]] = true;
            }
        }
    }
    for (int i = 0; i < total.size(); i++) {            //遍历,将false的人存入答案数组
        if (islove[total[i]] == false) {
            ans.push_back(total[i]);
        }
    }
    cout << ans.size() << endl;            //输出第一个数据,即答案数组的个数
    
    sort(ans.begin(),ans.end());            //照题目意思,从小到大排序
    for (int i = 0; i < ans.size(); i++) {        //最后输出答案,注意排版
        if (i == 0) {cout << ans[i];}
        else {cout << " " << ans[i];}
    }
    
}

文章来源:https://blog.csdn.net/yuzhou_ln/article/details/135281319
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。