题解 | 动态整数集最近值提取

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

set<int> s;

void insert(int x) {
    if (s.count(x)) {
        cout << "Already Exist\n";
    } else {
        s.insert(x);
    }
}

void extract(int x) {
    if (s.empty()) {
        cout << "Empty\n";
        return ;
    }

    auto it = s.lower_bound(x);
    int candidate1 = -1, candidate2 = -1;
    if (it != s.end()) {
        candidate1 = *it;
    }
    if (it != s.begin()) {
        candidate2 = *prev(it);
    }

    int selected;
    if (candidate1 == -1) {
        selected = candidate2;
    } else if (candidate2 == -1) {
        selected = candidate1;
    } else {
        int diff1 = abs(candidate1 - x);
        int diff2 = abs(candidate2 - x);
        if (diff1 < diff2) {
            selected = candidate1;
        } else if (diff1 > diff2) {
            selected = candidate2;
        } else {
            selected = min(candidate1, candidate2);
        }
    }

    s.erase(selected);
    cout << selected << '\n';
}

int main() {
    int Q, op, x;
    cin >> Q;
    while (Q--) {
        cin >> op >> x;
        if (op == 1) {
            insert(x);
        } else {
            extract(x);
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")