1995 破案
大约 3 分钟
1995 破案
【算法】 集合、查找、结构体
【C++】 set、tuple、结构体、pair
【难度】 入门
一、题目简述
某地连续发生盗窃案。已知犯罪团伙中每个人的身高、体重、年龄。警察想知道每个人是不是本市的(如果本市有人三项特征完全相同,就视为本市的)。
输入:
- ():本市人口数
- ():犯罪团伙人数
- 行:本市每个人的身高、体重、年龄
- 行:犯罪团伙每个人的身高、体重、年龄
对每个罪犯,如果特征与本市某人完全匹配,输出 yes,否则输出 no。
二、解题思路
2.1 问题本质
这本质上是一个集合查找问题:把本市所有人的特征存入集合,然后对每个罪犯查集合中是否存在相同特征。
2.2 数据规模分析
- (20 万),(1 万)
- 如果对每个罪犯都遍历全市人口(),最坏 次操作,会超时
- 需要用
set或unordered_set实现 或 的查找
2.3 用 set 存储特征
C++ 的 set 自动去重并支持快速查找。可以把三个特征组合成一个"键"存入 set。
方法一:用 tuple<int, int, int> 作为键
set<tuple<int, int, int>> s;
s.insert({h, w, age});
if (s.count({h, w, age})) ... // 查找方法二:用结构体 + 自定义比较函数
struct Person {
int h, w, age;
bool operator<(Person other) const {
if (h != other.h) return h < other.h;
if (w != other.w) return w < other.w;
return age < other.age;
}
};推荐方法一,tuple 已经内置了比较规则(逐元素比较),无需手写。
2.4 手动模拟
输入:
3 2
166 50 30
178 60 23
132 40 15
167 50 30
178 60 23本市人口集合:{(166,50,30), (178,60,23), (132,40,15)}
| 罪犯 | 特征 | 在本市? |
|---|---|---|
| #1 | (167,50,30) | ❌ no |
| #2 | (178,60,23) | ✅ yes |
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
set<tuple<int, int, int>> s; // 本市人口特征集合
for (int i = 0; i < n; i++) {
int h, w, age;
cin >> h >> w >> age;
s.insert({h, w, age});
}
for (int i = 0; i < m; i++) {
int h, w, age;
cin >> h >> w >> age;
if (s.count({h, w, age})) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
return 0;
}四、复杂度分析
- 时间复杂度:
- 建集合:, 次插入,每次
- 查询:, 次查找,每次
- 时,约 次操作,可以接受
- 空间复杂度:,存储本市所有人特征。
五、知识扩展
5.1 set vs unordered_set
set | unordered_set | |
|---|---|---|
| 底层 | 红黑树 | 哈希表 |
| 查找 | 平均 | |
| 有序 | 是 | 否 |
| 键要求 | 支持 < | 支持 hash |
如果用 unordered_set,tuple 默认有哈希支持(C++20),查找更快。但 set 写法更简单,对本题 完全够用。
5.2 为什么不用数组标记?
特征(身高、体重、年龄)的范围未给,可能很大。用三维数组标记(如 bool exist[200][200][200])不仅浪费空间,还可能越界。用 set 或 map 更安全。
