原题地址:

题目简述

给定一些序列（没有重复数字），每个序列支持：

给定一些数k（对于每个序列不重复），每次在序列里找到最接近k的数删除（如果有2个数字与k差一样，即分别是k-b和k+b，则选择较小的k-b），累加与k的差，输出。

---

思路

其实关键就是维护一个有序序列，支持插入，查询前继后继，删除指定数字。

自然我们会想到手打平衡树，Treap/Splay皆可。（这里只有旋转实现的Treap，非旋Treap（Split+Merge）和Splay日后加上）

Tips:为了防止越界等问题以及方便提取区间（尤其是Splay），序列前后一般塞上一个-INF和INF

然而作为C++选手，我们应该妙用STL。set可以实现这样的功能，内部是红黑树实现的也很快。

---

代码

1. 旋转实现的Treap(160ms,3.03MB)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int INF=1e9;inline int randad(){ static int seed=114514; return seed=int(seed*48271LL%2147483647);//48271使得随机数有完全周期，即2147483647内取遍不重复 }int delta=0;struct node { int pri,val,ch[2],size,tot;//pri:Treap的随机数//val:数字//ch[0,1]:左孩子右孩子//size:以该节点为根的子树里有几个数字//tot:这个数字出现了几次（本题无用）}T[111111];int k,size=0,ANS,ans;//k:根节点，size:树的大小,ANS:临时，ans:赶走了几个人void update(int k){T[k].size=T[T[k].ch[0]].size+T[T[k].ch[1]].size+T[k].tot;}void rturn(int &k)//右旋，把k旋到右边，k左孩子提到根{ int t=T[k].ch[0]; T[k].ch[0]=T[t].ch[1]; T[t].ch[1]=k; T[t].size=T[k].size; update(k); k=t;}void lturn(int &k)//左旋，把k旋到左边，k右孩子提到根{ int t=T[k].ch[1]; T[k].ch[1]=T[t].ch[0]; T[t].ch[0]=k; T[t].size=T[k].size; update(k); k=t;}void ins(int &k,int val) //插入{ if (k==0) { size++; k=size; T[k].pri=randad(); T[k].val=val; T[k].size=T[k].tot=1; return ; } T[k].size++; if (T[k].val==val) T[k].tot++; else if (val>T[k].val) { ins(T[k].ch[1],val); if (T[T[k].ch[1]].pri
          
           1) { T[k].tot--; T[k].size--; return ; } if (T[k].ch[0]==0||T[k].ch[1]==0) k=T[k].ch[0]+T[k].ch[1]; else if(T[T[k].ch[0]].pri
           
            T[k].val) T[k].size--,del(T[k].ch[1],val); else T[k].size--,del(T[k].ch[0],val);}int xth(int &k,int x)//查询第x小的数是什么 { if(k==0||x==0)return 0; if(x<=T[T[k].ch[0]].size) return xth(T[k].ch[0],x); else if(x>T[T[k].ch[0]].size+T[k].tot) return xth(T[k].ch[1],x-T[T[k].ch[0]].size-T[k].tot); else return T[k].val;}int find(int &k,int x)//查询第x小数在树中位置 { if (k==0||x==0) return 0; if(x<=T[T[k].ch[0]].size)return find(T[k].ch[0],x); if(x==T[T[k].ch[0]].size+1)return k; return find(T[k].ch[1],x-T[T[k].ch[0]].size-1);}void pre(int k,int x)//查询不比x大的且最接近x的数所在位置（x前继）{ if(k==0)return; if(T[k].val
            
             x) ANS=k,next(T[k].ch[0],x); else next(T[k].ch[1],x);}void Catch(int num)//匹配宠物和饲养人{ int a,b; pre(k,num),a=T[ANS].val; next(k,num), b=T[ANS].val; if(num-a<=b-num && a != -INF) { ans += num-a; del(k,a); } else { ans += b-num; del(k,b); } ans %= 1000000;}int main(){ int n; scanf("%d", &n); int cur; ins(k,-INF),ins(k,INF); for(int i = 1; i <= n; i++) { int a, b; scanf("%d%d", &a, &b); if(T[k].size == 2) { cur=a;//cur：当前是宠物等人认领还是人在等着接受宠物（看原题，不然谁看得懂啊= =） ins(k,b); } else if(a == cur) ins(k,b); else Catch(b); } printf("%d\n", ans); return 0; return 0;}
            
           
          
         
        
       
      
     
    

1. set实现(304ms,2.57MB)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
           #include 
          
           using namespace std;const int maxn = 1111111;const int INF = 1000000000;int n, ans;set 
           
             s;void find(int x) { set
            
             ::iterator left=--s.lower_bound(x),right=s.lower_bound(x);//lower_bound的实现是二分查找，迭代器指向不比x小的且最接近x的数的位置，所以left就是前继，right就是后继 if(x-*left<=*right-x&&*left!=-INF) { ans+=x-*left; s.erase(left); } else { ans+=*right-x; s.erase(right); } ans%=1000000;}int main() { scanf("%d",&n); int cur; s.insert(-INF),s.insert(INF); for(int i=1;i<=n;i++) { int a,b; scanf("%d%d", &a, &b); if(s.size()==2) { cur=a; s.insert(b); } else if(a==cur) s.insert(b); else find(b); } printf("%d\n", ans); return 0;}