PAT A1121 Damn Single(C++)

发表于 | 分类于 | |
字数统计: 822 字 | 阅读时长 ≈ 4 分钟
PAT甲级目录 | PAT乙级目录

题目描述

原题地址：A1121 Damn Single
中文版：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->first 和 it->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;
    }