轉載請注明出處,謝謝 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
SBT可解,貌似segment tree也可解。當作Splay練手,第一個Splay。
Splay每次把某個結點旋轉到根結點。旋轉分為三種。
如果父結點是根結點,那麼隻需要作一次左旋或者右旋即可,同SBT。
如果父結點P,P的父結點G,如果二者轉向相同,那麼連續兩次左旋或者右旋即可。
如果二者轉向不同,那麼向左旋後右旋或者先右旋後左旋,和SBT裡面的差不多。
不過這裡的旋轉好巧妙,代碼十分簡單。
對于這題,将每一個依次插入,與前驅和後繼進行比較,選取內插補點小的。如果遇到相同的數已經在樹中,則不插入。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 100005
#define inf 1<<29
using namespace std;
int pre[N],key[N],ch[N][2],root,tot1; //分别表示父結點,鍵值,左右孩子(0為左孩子,1為右孩子),根結點,結點數量
int n;
//建立一個結點
void NewNode(int &r,int father,int k){
r=++tot1;
pre[r]=father;
key[r]=k;
ch[r][0]=ch[r][1]=0; //左右孩子為空
}
//旋轉,kind為1為右旋,kind為0為左旋
void Rotate(int x,int kind){
int y=pre[x];
//類似SBT,要把其中一個分支先給父節點
ch[y][!kind]=ch[x][kind];
pre[ch[x][kind]]=y;
//如果父節點不是根結點,則要和父節點的父節點連接配接起來
if(pre[y])
ch[pre[y]][ch[pre[y]][1]==y]=x;
pre[x]=pre[y];
ch[x][kind]=y;
pre[y]=x;
}
//Splay調整,将根為r的子樹調整為goal
void Splay(int r,int goal){
while(pre[r]!=goal){
//父節點即是目标位置,goal為0表示,父節點就是根結點
if(pre[pre[r]]==goal)
Rotate(r,ch[pre[r]][0]==r);
else{
int y=pre[r];
int kind=ch[pre[y]][0]==y;
//兩個方向不同,則先左旋再右旋
if(ch[y][kind]==r){
Rotate(r,!kind);
Rotate(r,kind);
}
//兩個方向相同,相同方向連續兩次
else{
Rotate(y,kind);
Rotate(r,kind);
}
}
}
//更新根結點
if(goal==0) root=r;
}
int Insert(int k){
int r=root;
while(ch[r][key[r]<k]){
//不重複插入
if(key[r]==k){
Splay(r,0);
return 0;
}
r=ch[r][key[r]<k];
}
NewNode(ch[r][k>key[r]],r,k);
//将新插入的結點更新至根結點
Splay(ch[r][k>key[r]],0);
return 1;
}
//找前驅,即左子樹的最右結點
int get_pre(int x){
int tmp=ch[x][0];
if(tmp==0) return inf;
while(ch[tmp][1])
tmp=ch[tmp][1];
return key[x]-key[tmp];
}
//找後繼,即右子樹的最左結點
int get_next(int x){
int tmp=ch[x][1];
if(tmp==0) return inf;
while(ch[tmp][0])
tmp=ch[tmp][0];
return key[tmp]-key[x];
}
int main(){
while(scanf("%d",&n)!=EOF){
root=tot1=0;
int ans=0;
for(int i=1;i<=n;i++){
int num;
if(scanf("%d",&num)==EOF) num=0;
if(i==1){
ans+=num;
NewNode(root,0,num);
continue;
}
if(Insert(num)==0) continue;
int a=get_next(root);
int b=get_pre(root);
ans+=min(a,b);
}
printf("%d\n",ans);
}
return 0;
}