用set写真是轻松愉快；
#include<cstdio> #include<cstring> #include<set> #include<algorithm> using namespace std; set<int>st; int ans; int main() { int n,x; st.insert(-99999999); st.insert(99999999); scanf("%d",&n); for(int i=0; i<n; i++) { if(scanf("%d",&x)==EOF) x=0; if(i==0) { st.insert(x); ans+=x; } else { int y=min(*st.lower_bound(x)-x,x-*(--st.upper_bound(x))); if(y>0) { ans+=y; st.insert(x); } } } printf("%d ",ans); }
手写的treap
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; struct node { node *ch[2]; int r;//piority int v;//value int s;//rank bool operator<(const node &t)const { return r<t.r; } int cmp(int x)const { if(v==x)return -1; return x<v?0:1; } void maintain() { s=1; if(ch[0]!=NULL)s+=ch[0]->s; if(ch[1]!=NULL)s+=ch[1]->s; } }; void rotate(node* &root,int d)//0 for left,1 for right { node* k=root->ch[d^1]; root->ch[d^1]=k->ch[d]; k->ch[d]=root; root->maintain(); k->maintain(); root=k; } bool insert(node* &root,int x) { if(root==NULL) { root=new node(); root->ch[1]=NULL; root->ch[0]=NULL; root->v=x; root->r=rand(); } else { int d=root->cmp(x); if(d==-1)return 0; insert(root->ch[d],x); if(root->ch[d]>root)rotate(root,d^1); } return 1; } //void remove(node* &root,int x) //{ // int d=root->cmp(x); // if(d==-1) // { // if(root->ch[0]==NULL) // root=root->ch[1]; // else if(root->ch[1]==NULL) // root=root->ch[0]; // else // { // int d2=(root->ch[0]>root->ch[1]?1:0); // rotate(root,d2); // remove(root->ch[d2],x); // } // } // else remove(root->ch[d],x); //} int find(node* root,int x) { while(root!=NULL) { int d=root->cmp(x); if(d==-1)return 1; else root=root->ch[d]; } return 0; } void splay(node* &root,int x) { int d=root->cmp(x); if(d==1)x-=root->ch[0]->s+1; if(d!=-1) { node* p=root->ch[d]; int d2=p->cmp(x); int k2=(d2==0?x:x-p->ch[0]->s-1); if(d2!=-1) { splay(p->ch[d2],k2); if(d==d2)rotate(root,d^1); else rotate(root->ch[d],d); } rotate(root,d^1); } } int get_upper(node* root,int x) { node* p=root->ch[1]; if(p==NULL)return 9999999; while(p->ch[0]!=NULL) { p=p->ch[0]; } return p->v; } int get_lower(node* root,int x) { node* p=root->ch[0]; if(p==NULL)return 99999999; while(p->ch[1]!=NULL) { p=p->ch[1]; } return p->v; } int main() { int n,x,ans=0; node *root=new node(); root=NULL; bool flag=1; scanf("%d",&n); while(n--) { if(scanf("%d",&x)==EOF) x=0; if(flag) { insert(root,x); ans+=x; flag=0; } else { if(find(root,x)==1)continue; insert(root,x); ans+=min(abs(get_upper(root,x)-x),abs(x-get_lower(root,x))); } } printf("%d ",ans); }