题目思路：splay,用到了查找树内某结点的前驱，后继和插入操作。
[cpp] #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define inf 0x3f3f3f3f #define Max 40000 int max(int a,int b) { return a>b a:b; } int min(int a,int b) { return a } int p[Max],ch[Max][2],val[Max],root,top1; inline void newnode(int &x,int fa,int data) { x=++top1; p[x]=fa,val[x]=data; ch[x][0]=ch[x][1]=0; } inline void rot(int x,int f) { int y=p[x]; ch[y][!f]=ch[x][f]; p[ch[x][f]]=y; if(p[y]) ch[p[y]][ch[p[y]][1]==y]=x; p[x]=p[y]; ch[x][f]=y; p[y]=x; } inline void splay(int x,int goal) { while(p[x]!=goal) { if(p[p[x]]==goal) rot(x,ch[p[x]][0]==x); else { int y=p[x]; int f=(ch[p[y]][0]==y); if(ch[y][f]==x) { rot(x,!f),rot(x,f); } else { rot(y,f),rot(x,f); } } } if(goal==0) root=x; } inline int pre(int x) { int tmp=ch[x][0]; if(tmp==0) return inf; www.2cto.com while(ch[tmp][1]) { tmp=ch[tmp][1]; } return val[x]-val[tmp]; } inline int suc(int x) { int tmp=ch[x][1]; if(tmp==0) return inf; while(ch[tmp][0]) tmp=ch[tmp][0]; return val[tmp]-val[x]; } inline int ins(int data) { int x=root; while(ch[x][val[x] { if(val[x]==data) { splay(x,0); return 0; } x=ch[x][val[x] } newnode(ch[x][val[x] splay(ch[x][val[x] return 1; } int main() { int n,a,b,ans,i,tmp; while(scanf("%d",&n)!=EOF) { ans=0; top1=0; for(i=1;i<=n;i++) { if(scanf("%d",&tmp)==EOF) tmp=0; if(i==1) { newnode(root,0,tmp); ans+=tmp;continue; } if(ins(tmp)==0)continue; a=pre(root); b=suc(root); if(a ans+=a; else ans+=b; } printf("%d\n",ans); } }