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

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

int main() {
    int q;
    cin>>q;
    set<int>st;
    for(int i=0;i<q;i++)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x;
            cin>>x;
            if(st.count(x)==0)
            {
                st.insert(x);
            }
            else
            {
                cout<<"Already Exist"<<endl;
            }
        }
        if(op==2)
        {
            int x;
            cin>>x;
            if(st.empty()==true)
            {
                cout<<"Empty"<<endl;
            }
            else 
            {
                // 情形1 x大于等于最大值
                if(x>=*(--st.end()))
                {
                    cout<<*(--st.end())<<endl;
                    st.erase(*(--st.end()));
                }
                // 情形2 x小于等于最小值
                else if(x<=*st.begin())
                {
                    cout<<*st.begin()<<endl;
                    st.erase(*st.begin());
                }
                // 情形3 x在元素中间的
                else
                {
                    // 分支1 只有一个元素时
                    if(st.size()==1)
                    {
                        cout<<*st.begin()<<endl;
                        st.erase(*st.begin());
                    }
                    // 分支2 有两个元素时
                    else if(st.size()==2)
                    {
                        int big=*(--st.end());
                        int small=*st.begin();
                        if(big-x<x-small)
                        {
                            cout<<big<<endl;
                            st.erase(big);
                        }
                        else 
                        {
                            cout<<small<<endl;
                            st.erase(small);
                        }
                    }
                    // 分支3 有2个以上元素时
                    else
                    {
                        auto it1=st.lower_bound(x);
                        int big=*it1;
                        it1--;
                        auto it2=it1;
                        int small=*it2;
                        if(big-x<x-small)
                        {
                            cout<<big<<endl;
                            st.erase(big);
                        }
                        else 
                        {
                            cout<<small<<endl;
                            st.erase(small);
                        }
                    }
                }
            }
        }
    }
}
// 64 位输出请用 printf("%lld")