PAT B1065 单身狗(C++)

PAT甲级目录 | PAT乙级目录

题目描述

B1065 单身狗

解题思路

方法一:利用 map 记录每对对象的编号。然后遍历全部客人,如果其没有对象或者其对象没来,则加入落单名单。

方法二:假设所有客人都落单。在遍历客人的时候,如果在落单名单中找到了自己对象,则移除其对象编号,否则当作落单加入名单。遍历结束时,名单中的人要么没有对象,要么对象没来,也就正好落单了。

易错点

  • 客人编号有 00000 ,所以不能通过 map 对应的值是否大于零来判断其是否单身
  • 输出的编号应为格式化为五位数 printf("%05d", *it);

也许陌生的知识点

  • map<int, int> m;
    • 用于映射,键和值可以是任意类型
    • 直接使用 m[<键>] = <值> 即可向map中添加一组键值对
    • 需要的头文件:map
  • for(auto it = m.begin(); it != m.end(); it++){}
    • 可用于遍历 map/vector/set 等容器, auto 实现自动匹配对应迭代器类型
    • 如果不用 auto it = m.begin() 则要写成 std::map<char, int>::iterator it = m.begin()
    • map<char,int> 在其他情况下可替换成对应元素的类型如 vector<int>
    • 所需头文件: map / set / vector
  • it->firstit->second
    • it->first 为 map 中对应元素的关键字
    • it->second 为 map 中对应关键字的值
    • 所需头文件: map
  • if(couple.find(id1) == couple.end()){ }
    • couple.find(id1) 函数可用于查找序列中是否有某元素,如找到则返回元素迭代器,如未找到则返回 couple.end()
    • 包含该函数的容器:map, set
  • ans.insert(S[i])
    • 向容器中插入一个元素
  • 所需头文件: set
  • ans.erase(it)
    • 删除集合中某元素,it 为迭代器
  • 需要头文件: set

代码示例:

  • 方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <map>
#include <set>
using namespace std;
int main(){
int n, m, id1, id2;
map<int, int> couple, present;
set<int> ans;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d %d", &id1, &id2);
couple[id1] = id2;
couple[id2] = id1;
}
scanf("%d", &m);
for(int i = 0; i < m; i++){
scanf("%d", &id1);
present[id1] = 1; // 记录每个出现的客人编号
}
for(auto it = present.begin(); it != present.end(); it++){
id1 = it->first;
id2 = couple[id1];
if(couple.find(id1) == couple.end() || !present[id2]) ans.insert(id1);//客人没有对象或者对象没来就加入清单
}
printf("%d\n", ans.size());
for(auto it = ans.begin(); it != ans.end(); it++){
if(it != ans.begin()) printf(" ");
printf("%05d", *it);
}
return 0;
}
  • 方法二:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #include <cstdio>
    #include <map>
    #include <set>
    using namespace std;
    int main() {
    int n, m, id1, id2;
    map<int, int> couple;
    set<int> ans;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
    scanf("%d %d", &id1, &id2);
    couple[id1] = id2;
    couple[id2] = id1;
    }
    scanf("%d", &m);
    for(int i = 0; i < m; i++){
    scanf("%d", &id1);
    id2 = couple[id1];
    // 新来的客人在此派对中找到了对象,将对方名字从名单中抹去,否则将其加入名单
    if(!ans.empty() && ans.find(id2) != ans.end()) ans.erase(ans.find(id2));
    else ans.insert(id1);
    }
    printf("%d\n", ans.size());
    for(auto it = ans.begin(); it != ans.end(); it++){
    if(it != ans.begin()) printf(" ");
    printf("%05d", *it);
    }
    return 0;
    }