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

#include<bits/stdc++.h>
using namespace std;
set<int> s;
int main() {
    int Q;
    int temp;
    cin >> Q;
    while (Q--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            if (s.count(x) == 0)
                s.insert(x);
            else cout << "Already Exist\n";
        }
        if (op == 2) {
            if (s.empty()) {
                cout << "Empty\n";
            } else {
                auto it = s.lower_bound(x);//遍历s取第一个大于等于x的数
                int ans;
                if (it == s.end()) {
                    ans = *(--it);//如果集合s中所有数都小于x，则取最后一个
                } else if (it == s.begin()) {
                    ans = *it;//如果集合s中所有数都大于x，则取第一个
                } else {
                    int a = *it;
                    int b = *(prev(it));//b用来储存上一个it的地址
                    if (abs(a - x) < abs(b - x)) {
                        ans = a;
                    } else if (abs(a - x) > abs(b - x)) {
                        ans = b;
                    } else {
                        ans = min(a, b);  // 差值相同时取较小的
                    }
                }
                cout << ans << "\n";
                s.erase(ans);
            }
        }
    }
    return 0;
}