题意：给出一个n个数的数列a,对于第i个元素ai定义fi=min(abs(ai-aj))，(1<=j<i)，其中f1=a1。输出sum(fi) (1<=i<=n)
// File Name: 1588.cpp // Author: Zlbing // Created Time: 2013年08月09日 星期五 12时21分58秒 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 0x3f3f3f3f #define LL long long #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) const int MAXN=200010; const int mod=1000000; struct SplayTree { int sz[MAXN]; int ch[MAXN][2]; int pre[MAXN]; int rt,top; inline void up(int x){ sz[x] = cnt[x] + sz[ ch[x][0] ] + sz[ ch[x][1] ]; } inline void Rotate(int x,int f){ int y=pre[x]; ch[y][!f] = ch[x][f]; pre[ ch[x][f] ] = y; pre[x] = pre[y]; if(pre[x]) ch[ pre[y] ][ ch[pre[y]][1] == y ] =x; ch[x][f] = y; pre[y] = x; up(y); } inline void Splay(int x,int goal){//将x旋转到goal的下面 while(pre[x] != goal){ if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][0] == x); else { int y=pre[x],z=pre[y]; int f = (ch[z][0]==y); if(ch[y][f] == x) Rotate(x,!f),Rotate(x,f); else Rotate(y,f),Rotate(x,f); } } up(x); if(goal==0) rt=x; } inline void RTO(int k,int goal){//将第k位数旋转到goal的下面 int x=rt; while(sz[ ch[x][0] ] != k-1) { if(k < sz[ ch[x][0] ]+1) x=ch[x][0]; else { k-=(sz[ ch[x][0] ]+1); x = ch[x][1]; } } Splay(x,goal); } inline void vist(int x){ if(x){ printf("结点%2d : 左儿子 %2d 右儿子 %2d %2d sz=%d ",x,ch[x][0],ch[x][1],val[x],sz[x]); vist(ch[x][0]); vist(ch[x][1]); } } inline void Newnode(int &x,int c){ x=++top; ch[x][0] = ch[x][1] = pre[x] = 0; sz[x]=1; cnt[x]=1; val[x] = c; } inline void init(){ ch[0][0]=ch[0][1]=pre[0]=sz[0]=0; rt=top=0; cnt[0]=0; Newnode(rt,-INF); Newnode(ch[rt][1],INF); pre[top]=rt; sz[rt]=2; } inline void Insert(int &x,int key,int f){ if(!x) { Newnode(x,key); pre[x]=f; Splay(x,0);//效率的保证 return ; } if(key==val[x]){ cnt[x]++; sz[x]++; Splay(x,0);//不加会超时，囧啊 return ; }else if(key<val[x]) { Insert(ch[x][0],key,x); } else { Insert(ch[x][1],key,x); } up(x); } void findpre(int x,int key,int &ans){ if(!x) return ; if(val[x] <= key){ ans=val[x]; findpre(ch[x][1],key,ans); } else findpre(ch[x][0],key,ans); } void findsucc(int x,int key,int &ans){ if(!x) return ; if(val[x]>=key) { ans=val[x]; findsucc(ch[x][0],key,ans); } else findsucc(ch[x][1],key,ans); } int cnt[MAXN]; int val[MAXN]; }spt; int main() { int n; scanf("%d",&n); spt.init(); int ans=0; int a; scanf("%d",&a); spt.Insert(spt.rt,a,0); ans=a; n--; while(n--) { a=0;//不知道为什么这里要赋值为0，不赋值就wa!! scanf("%d",&a); int x,y; spt.findpre(spt.rt,a,x); spt.findsucc(spt.rt,a,y); if(abs(a-x)<=abs(a-y)) { ans+=abs(a-x); } else { ans+=abs(a-y); } spt.Insert(spt.rt,a,0); } printf("%d ",ans); return 0; }