1 条题解
-
0
邻近坐标:解题说明
用
set<long long>保持坐标有序。insert自动忽略重复,erase(x)返回删除的元素个数,恰好就是需要的 0 或 1。查询时先处理空集合,再用集合成员函数
lower_bound(x)找第一个大于等于 x 的坐标。若返回 begin,仅需考虑该坐标;若返回 end,仅需考虑最后一个坐标;否则比较这个坐标与prev得到的前驱。前驱以外更小的坐标只会更远,后继以外更大的坐标也只会更远,所以候选完整。左侧距离小于等于右侧距离时选左侧,落实同距离取较小值。使用 long long 计算距离。每次操作 O(log q),总时间 O(q log q),空间 O(q)。
常见错误:空集合时解引用迭代器;对 begin 取前驱;解引用 end;相同距离选择较大坐标;使用通用
lower_bound对 set 迭代器查找,导致线性移动。验证期望由独立 Python 算法生成,不读取参考程序。样例先手算,再以空实现确认测试失败;正式数据包含边界、固定种子随机及两个最大规模用例。
C++17 参考实现
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin>>q; set<long long> points; while(q--) { string op; long long x; cin>>op>>x; if(op=="INSERT") { points.insert(x); } else if(op=="ERASE") { cout<<points.erase(x)<<'\n'; } else { if(points.empty()) { cout<<"EMPTY\n"; continue; } auto right=points.lower_bound(x); if(right==points.begin()) cout<<*right<<'\n'; else if(right==points.end()) cout<<*prev(right)<<'\n'; else { long long l=*prev(right),r=*right; cout<<(x-l<=r-x?l:r)<<'\n'; } } } return 0; }
- 1
信息
- ID
- 5270
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者