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

#include <iostream>
#include <set>
//本题主要考察对集合指令中指针的理解，如find函数，begin函数和end函数，
//区别于栈和队列的是，在集合中这些函数的值以指针的形式出现，引用是需要用到*运算符
using namespace std;

int main() {
    int Q{};//对集合进行q次操作
    cin>>Q;
    set<int> a;//定义一个集合
    while(Q--)
    {
        int op{};//定义操作类型
        
        cin>>op;
        if(op==1)//对于操作1
        {
            long long x{};//依据x的取值范围定义x为long long
            cin>>x;
            if(a.empty())//先检查集合是否非空
            {
                a.insert(x);//空集合直接插入
            }
            else
            {    
                if(a.find(x)==a.end())//非空则检查是否已有元素x
                {
                    a.insert(x);//这里的判断是无，因为返回了null元素的指针
                }
                else {
                    cout<<"Already Exist"<<endl;//否则输出已存在元素x
                }
            }

        }

        if(op==2)//对于操作2
        {
            long long x;
            cin>>x;
            if(!a.empty())//先检查集合是否非空，养成好习惯
            {
                if(x>=*--a.end()){//这里处理了x大于集合里所有元素的情况
                    cout<<*--a.end()<<endl;//使用--end是因为指针指向的是集合最后一个元素的后一个
				  							//也就是null，所以往前移一位
                    a.erase(*--a.end());
                    continue;
                }
                else if(x<=*a.begin())//这里处理了x小于集合里所有元素的情况，原理同上
                {
                    cout<<*a.begin()<<endl;
                    a.erase(*a.begin());
                    continue;
                }

                auto p=a.lower_bound(x);//这里我们想要处理一般情况，定义一个大于等于x的元素指针
                int u=*p,v=*--p;//这里一定要另设变量来处理指针，因为--运算符会导致指针自减，
			  //笔者因此导致了报错，因此使用--运算符需要格外注意
			  
                
                if(abs(u-x)>=abs(v-x))//比较两者绝对值的差
                {
                    cout<<v<<endl;
                    a.erase(v);//谁小输出谁，下面同理
                    
                }
                else {
                    cout<<u<<endl;
                    a.erase(u);
                }
            }
            else
            {
                cout<<"Empty"<<endl;//这里的else对应最上面的if，此时集合为空
            }
            
        }



    }




    return 0;
}
// 64 位输出请用 printf("%lld")