莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 每次找当前数的前驱和后继，记录差值最小的数值
2. 注意：本题的前驱和后继并不严格大小于

可参考： 普通平衡树

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 33010, INF = 0x3f3f3f3f;

int n;
int root,idx;
struct Node
{
    int l,r;
    int key,val;
}tr[N];

//建立新节点
int get_node(int key)
{
    tr[++idx].key=key;
    tr[idx].val=rand();
    return idx;
}

//初始化 Treap
void build()
{
    int root=get_node(-INF);
    tr[1].r=get_node(INF);
}

//右旋
void zig(int &p)
{
    int q=tr[p].l;
    tr[p].l=tr[q].r,tr[q].r=p,p=q;
}

//左旋
void zag(int &p)
{
    int q=tr[p].r;
    tr[p].r=tr[q].l,tr[q].l=p,p=q;
}

//插入操作
void insert(int &p,int key)
{
    if(!p) p=get_node(key);
    else if(tr[p].key==key) return;
    else if(tr[p].key>key)
    {
        insert(tr[p].l,key);
        if(tr[tr[p].l].val>tr[p].val) zig(p);
    }
    else 
    {
        insert(tr[p].r,key);
        if(tr[tr[p].r].val>tr[p].val) zag(p);
    }
}

//找前驱
int get_prev(int p,int key)
{
    if(!p) return -INF;
    if(tr[p].key>key) return get_prev(tr[p].l,key);
    return max(tr[p].key,get_prev(tr[p].r,key));
}

//找后继
int get_next(int p,int key)
{
    if(!p) return INF;
    if(tr[p].key<key) return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));
}

int main()
{
    build();

    cin>>n;

    LL res=0;
    for(int i=1;i<=n;i++) 
    {
        int x;
        cin>>x;
        if(i==1) res+=x;
        else res+=min(x-get_prev(root,x),get_next(root,x)-x);
        insert(root,x);
    }

    cout<<res<<endl;

    return 0;
}