1 条题解

  • 0
    @ 2026-11-16 20:48:26

    邻近坐标:解题说明

    用 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
    上传者