#STL017. 邻近坐标
邻近坐标
邻近坐标
导航面板保存一些一维整数坐标,初始没有坐标。你可以插入或删除坐标,也可以查询某个位置附近最近的现存坐标。相同距离时,面板固定选择较小的坐标。
依次处理所有操作。
输入格式
第一行一个整数 q。接下来 q 行,每行是以下一种操作:
INSERT x:插入坐标 x,已经存在则忽略,不输出。ERASE x:删除坐标 x,存在且删除成功输出 1,否则输出 0。NEAR x:输出与 x 距离最近的现存坐标;相同距离取较小者。集合为空时输出EMPTY。
输出格式
按照操作顺序,每个 ERASE 或 NEAR 的结果独占一行。只有 INSERT 操作时,可以没有输出。
数据范围与约定
- 1≤q≤200000。
- 所有 x 在 [−1000000000,1000000000] 中。
- 集合只保存不同坐标。距离定义为绝对值 |坐标−x|。
样例 1
输入:
10
NEAR 0
INSERT 5
INSERT -5
NEAR 0
INSERT 5
ERASE 8
ERASE -5
NEAR 0
ERASE 5
NEAR 1
输出:
EMPTY
-5
0
1
5
1
EMPTY
说明:首次查询时为空。插入 5 与 −5 后,0 到二者距离相同,选 −5。重复插入 5 不增加元素;删除不存在的 8 返回 0。最后两个坐标都被删除,查询再次返回 EMPTY。
样例 2
输入:
7
INSERT 1
INSERT 3
NEAR 2
NEAR 4
ERASE 1
NEAR 0
ERASE 1
输出:
1
3
1
3
0
说明:2 到 1 和 3 距离相同,选 1;4 最近的是 3。删除 1 后,0 只能返回 3;再次删除 1 返回 0。
原创说明
本题的场景、题面、样例、实现与数据由本题单作者独立编写;仅使用公开的算法概念与 C++ 标准库接口,未使用第三方题面或测试文件。