题目

链接：https://ac.nowcoder.com/acm/contest/19850/L 来源：牛客网

HA实验有一套非常严密的安全保障体系，在HA实验基地的大门，有一个指纹锁。

该指纹锁的加密算法会把一个指纹转化为一个不超过1e7的数字，两个指纹数值之差越小，就说明两个指纹越相似，当两个指纹的数值差≤k时，这两个指纹的持有者会被系统判定为同一个人。现在有3种操作，共m个，操作1：add x，表示为指纹锁录入一个指纹，该指纹对应的数字为x，如果系统内有一个与x相差≤k的指纹，则系统会忽略这次添加操作操作2：del x，表示删除指纹锁中的指纹x，若指纹锁中多个与x相差≤k的指纹，则全部删除，若指纹锁中没有指纹x，则可以忽略该操作，操作3：query x，表示有一个持有指纹x的人试图打开指纹锁，你需要设计一个判断程序，返回该人是否可以打开指纹锁（只要x与存入的任何一个指纹相差≤k即可打开锁）。初始状态，指纹锁中没有任何指纹。

输入描述:
1
2
第一行有2个正整数m，k。
接下来m行，每行描述一种操作：add x，del x或query x。
输出描述:
1
对于每个query操作，输出一行，包含一个单词“Yes”或“No”，表示该人是否可以打开指纹锁。

 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


#include <iostream>
#include <set>
using namespace std;

int m,k;
struct cmp
{
    bool operator()(const int &a,const int &b) const
    {
        if(abs(a-b) <= k) return false;
        return a < b;
    }
};
int main()
{
    ios::sync_with_stdio(false);
    cin >> m >> k;
    set<int,cmp> prin;
    while(m--)
    {
        string op;int x;
        cin >> op >> x;
        if(op == "add") prin.insert(x);
        else if(op == "del") prin.erase(x); 
        else if(prin.find(x) != prin.end()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

在这个例子中，使用set进行了元素的增删查，其中巧妙的运用了重载运算符完美契合题目的思路

set 是 C++ 标准库（STL）中的一个关联容器，提供了一种自动排序且不允许重复元素的数据结构。它基于红黑树实现，支持高效的插入、删除和查找操作，时间复杂度约为 O(log n)。

set 的基本使用

set 主要包含以下功能：

自动排序（默认升序）
不允许重复元素（可重复者有multiset）
插入、删除、查找操作时间复杂度为 O(log n)
支持范围操作

声明和初始化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {5, 2, 8, 3, 1};  // 自动排序，结果是 {1, 2, 3, 5, 8}

    // 遍历 set
    for (int x : s) {
        cout << x << " ";  // 输出: 1 2 3 5 8
    }
    cout << endl;

    return 0;
}

说明：

set 内部自动按照从小到大排序（默认按 operator< 排序）
不能存储重复值，如果尝试插入相同元素，会被自动忽略。

set 的常见操作

插入元素

1
2
3
4
5
6
7
8
9


set<int> s;
s.insert(10);
s.insert(5);
s.insert(20);
s.insert(10);  // 插入相同元素无效

for (int x : s) {
    cout << x << " ";  // 输出: 5 10 20
}

insert(x): 插入元素 x，如果已存在，则不会插入。

查找元素

1
2
3
4
5


if (s.find(10) != s.end()) {
    cout << "10 存在" << endl;
} else {
    cout << "10 不存在" << endl;
}

find(x): 返回迭代器，指向 x 所在位置；如果 x 不存在，返回 s.end()。

删除元素

1

s.erase(10);  // 删除 10

erase(x): 删除 x，如果 x 存在，则移除它；否则无操作。

计数

1

cout << s.count(10);  // 0（不存在）或 1（存在）

count(x) 只返回 0 或 1，因为 set 不能有重复值。

lower_bound 和 upper_bound

1
2
3
4
5
6
7


set<int> s = {10, 20, 30, 40, 50};

auto it = s.lower_bound(25);  // 第一个 >= 25 的元素
cout << *it << endl;  // 输出 30

it = s.upper_bound(30);  // 第一个 > 30 的元素
cout << *it << endl;  // 输出 40

lower_bound(x): 返回第一个大于等于 x 的元素迭代器。
upper_bound(x): 返回第一个大于 x 的元素迭代器。

equal_range()

1
2


auto [l,r] = s.equal_range(1);
cout << *l << *r;

表示第一个大于或等于给定关键值的元素和第一个大于给定关键值的迭代器

返回最大最小值

1
2


cout << *s.begin();
cout << *s.rbegin();

其它

1
2
3
4
5


s.clear() //清空
s.empty() //检查set是否为空
s.begin();s.end(); //set中正向的返回指向开始和结束位置的迭代器
s.rbegin();s.rend(); //set中反向
s.size();

set 的高级用法

自定义排序

默认情况下，set 按升序排列。如果要降序排序，可以使用 greater：

1
2
3
4


set<int, greater<int>> s = {10, 5, 20, 15};
for (int x : s) {
    cout << x << " ";  // 输出: 20 15 10 5
}

也可以使用自定义比较函数：

1
2
3
4
5
6


struct cmp {
    bool operator()(const int &a, const int &b) const {
        return a > b;  // 降序
    }
};
set<int, cmp> s = {10, 5, 20, 15};

set 维护结构体

如果 set 存储结构体类型，需要定义比较规则：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


struct Student {
    string name;
    int score;

    // 自定义排序规则（按成绩升序）
    bool operator<(const Student &s) const {
        return score < s.score;
    }
};

set<Student> s;
s.insert({"Alice", 90});
s.insert({"Bob", 85});
s.insert({"Charlie", 95});

for (auto x : s) {
    cout << x.name << " " << x.score << endl;
}

需要定义 operator<，否则 set 无法自动排序。

unordered_set

如果不需要排序，可以使用 unordered_set，它基于哈希表，插入、删除、查找的时间复杂度为 O(1)：

1
2


#include <unordered_set>
unordered_set<int> us = {10, 5, 20, 15};

但 unordered_set 无法使用 lower_bound、upper_bound。

但同样支持insert erase find count empty size clear

multiset（允许重复元素）

如果需要存储重复元素，可以使用 multiset：

1
2
3
4
5


multiset<int> ms = {10, 5, 10, 20, 5};

for (int x : ms) {
    cout << x << " ";  // 输出: 5 5 10 10 20
}

multiset.erase(10) 会删除所有 10；
如果只想删除一个 10，可以用 ms.erase(ms.find(10))。

其余函数和set基本相同

总结

操作	set	unordered_set	multiset
排序	自动排序	无序	自动排序
允许重复	❌	❌	✅
插入删除查找	O(log n)	O(1)	O(log n)
适用场景	需要排序	只需快速查找	需要排序且允许重复

STL-Set的使用

Set的常用操作以及重载运算符

题目