PAT A1149 Dangerous Goods Packaging(C++)

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

题目描述

原题地址：A1149 Dangerous Goods Packaging
中文版：B1090 危险品装箱

题目描述

集装箱运输货物时，我们必须特别小心，不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱，否则很容易造成爆炸。

本题给定一张不相容物品的清单，需要你检查每一张集装箱货品清单，判断它们是否能装在同一只箱子里。

输入格式：

输入第一行给出两个正整数：$N(\le10^4)$ 是成对的不相容物品的对数；$M(\le100)$ 是集装箱货品清单的单数。

随后数据分两大块给出。第一块有 N 行，每行给出一对不相容的物品。第二块有 M 行，每行给出一箱货物的清单，格式如下：

1
K G[1] G[2] ... G[K]

其中 $K (\le1000)$ 是物品件数，G[i] 是物品的编号。简单起见，每件物品用一个 5 位数的编号代表。两个数字之间用空格分隔。

输出格式：

对每箱货物清单，判断是否可以安全运输。如果没有不相容物品，则在一行中输出 Yes，否则输出 No。

解题思路

用可变二维数组保存不相容的物品清单。对于每一箱，遍历要放入该箱的货物，每个货物查找对应的不相容物品清单，并搜查箱子内现有物品。如果在箱子里找到了与该货物不相容的物品，则结束循环并输出信息；如果没找到，则该物品说明安全，将其加入箱子。

也许陌生的知识点

  • ans.insert(S[i])
    • 向集合中插入一个元素
  • 需要头文件 set
  • ans.erase(it)
    • 删除集合中某元素，it 为迭代器
  • 需要头文件 set
  • if(ans.find(c) == ans.end()){ }
    • ans.find(id1) 函数可用于查找序列中是否有某元素，如找到则返回元素迭代器，如未找到则返回 ans.end()
    • 包含该函数的容器：map, 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
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int maxn = 100000;
int main(){
  int N, M, x, y;
  vector<int> G[maxn];
  cin >> N >> M;
  for(int i = 0; i < N; i++){
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  for(int i = 0; i < M; i++){
    int k, id, valid = 1;
    set<int> s;
    cin >> k;
    for(int j = 0; j < k; j++){
      cin >> id;
      for(int l = 0; valid == 1 && l < G[id].size(); l++){
        if(s.find(G[id][l]) != s.end()) valid = 0;
      }
      s.insert(id);
    }
    if(valid == 0) cout << "No\n";
    else cout << "Yes\n";
  }
  return 0;
}