解题思路：找边上最近的值。
解题思路：splay
解题代码：
1 // File Name: poj3468.sz.cpp 2 // Author: darkdream 3 // Created Time: 2014年11月07日 星期五 08时45分48秒 4 #include<limits.h> 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define maxn 1000010 26 using namespace std; 27 #define valtree ch[ch[root][1]][0] 28 struct SplayTree{ 29 int ch[maxn][2]; 30 int pre[maxn]; 31 int root ; 32 int top1; 33 inline void Rotate(int x ,int f){ 34 int y = pre[x]; 35 ch[y][!f] = ch[x][f]; 36 pre[ch[x][f]] = y ; 37 pre[x] = pre[y]; 38 if(pre[x]) 39 ch[pre[y]][ch[pre[y]][1] == y] = x; 40 ch[x][f] = y ; 41 pre[y] = x; 42 } 43 void Splay(int x, int goal){ 44 while(pre[x] != goal){ 45 if(pre[pre[x]] == goal){ 46 Rotate(x,ch[pre[x]][0] == x); 47 }else{ 48 int y = pre[x],z = pre[y]; 49 int f = (ch[z][0] == y); 50 if(ch[y][f] == x) 51 { 52 Rotate(x,!f),Rotate(x,f); 53 }else{ 54 Rotate(y,f),Rotate(x,f); 55 } 56 } 57 } 58 if(goal == 0 ) root = x; 59 } 60 int ABS(int x) 61 { 62 if(x < 0) 63 return -x; 64 return x ; 65 } 66 int Rotateto(int k ,int goal) 67 { 68 int r = root ; 69 int mi = INT_MAX; 70 while(1) 71 { 72 mi = min(mi,ABS(val[r]-k)); 73 if(!ch[r][val[r] < k]) 74 break; 75 r = ch[r][val[r] < k ]; 76 } 77 int &tt = ch[r][val[r] < k]; 78 newnode(tt,k); 79 pre[tt] = r; 80 Splay(tt,0); 81 return mi; 82 } 83 /*void erase(int x ){ 84 int father = pre[x]; 85 int head = 0 , tail = 0 ; 86 for() 87 }*/ 88 /*void debug(){printf("%d ",root);Treaval(root);} 89 void Treaval(int x) { 90 if(x) { 91 Treaval(ch[x][0]); 92 printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2d sum = %3lld ",x,ch[x][0],ch[x][1],pre[x],sz[x],val[x],sum[x]); 93 Treaval(ch[x][1]); 94 } 95 }*/ 96 void newnode(int &x,int c) 97 { 98 x = ++ top1; 99 ch[x][0] = ch[x][1] = pre[x] = 0 ; 100 val[x] = c; 101 } 102 void init(int v) 103 { 104 ch[0][0] = ch[0][1] = pre[0] =0 ; 105 root = top1 = 0 ; 106 newnode(root,v); //这里注意 root 是从1 开始的 107 } 108 int val[maxn]; 109 }sp; 110 int main(){ 111 int n ; 112 scanf("%d",&n); 113 if(n == 0 ) 114 { 115 printf("%d ",0); 116 return 0; 117 } 118 int v; 119 scanf("%d",&v); 120 sp.init(v); 121 int ans = v; 122 for(int i = 1;i < n;i ++) 123 { 124 if(scanf("%d",&v) == EOF) 125 v = 0 ; 126 ans += sp.Rotateto(v,0); 127 } 128 printf("%d ",ans); 129 return 0; 130 }