牛客竞赛算法入门题单打卡 L 指纹锁

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
?

题目描述

????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即可打开锁）。
????初始状态，指纹锁中没有任何指纹。
?

输入描述:

第一行有2个正整数m，k。
接下来m行，每行描述一种操作：add x，del x或query x。

输出描述:

对于每个query操作，输出一行，包含一个单词“Yes”或“No”，表示该人是否可以打开指纹锁。

示例1

输入

复制4 3 add 1 add 10 query 5 query 4

4 3
add 1
add 10
query 5
query 4

输出

复制No Yes

No
Yes

示例2

输入

复制4 3 add 1 query 4 del 1 query 4

4 3
add 1
query 4
del 1
query 4

输出

复制Yes No

Yes
No

示例3

输入

复制6 3 add 10 query 10 add 5 query 5 del 7 //系统将指纹10和指纹5全部删除 query 8

6 3
add 10
query 10
add 5 
query 5
del 7		//系统将指纹10和指纹5全部删除
query 8

输出

复制Yes Yes No

Yes
Yes
No

备注:

对于100%的测试数据：
1 ≤ k,m ≤ 1000000
数据量较大，注意使用更快的输入输出方式。

思路

根据题目，可以想到利用set来解决问题。写一个cmp函数来重载set排序规律。

#include<bits/stdc++.h>
using namespace std;
int k;
struct cmp{//重载set
	bool operator()(const int& a,const int&b)const
	{
		if(abs(a-b)<=k)return false;//表示不进入set
		return a<b;
	}
};
int main()
{
	int m;
	scanf("%d%d",&m,&k);//题目要求更快的输入方式
	set<int,cmp>s;
	for(int i=0;i<m;i++)
	{
		string opt;
		cin>>opt;
		int x;
		scanf("%d",&x);
		if(opt=="add")s.insert(x);
		else if(opt=="del")s.erase(x);
		else {
			if(s.find(x)!=s.end())printf("Yes\n");
			else printf("No\n");
		}
	}
	
}