Description

题意：给定 n个数，每给定一个数，在之前的数里找一个与当前数相差最小的数，求相差之和（第一个数为它本身）

如：5 1 2 5 4 6

Ans=5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

n<=32767

Solution

平衡树入门题，每读入一个数，将当前数旋转至树根 ，在左子树中找一个最大以及右子树中最小的与根进行比较即可

Code

#include 
    
     #include 
     
      #define N 33333#define Inf 0x7fffffff/2//会爆int#define lc(x) ch[(x)][0]using namespace std;int n,root,tmp,fa[N],ch[N][2],k[N],ind=1,Ans;//k[]下标节点储存的值inline void rotate(int p){//旋转    int q=fa[p],y=fa[q],x=(ch[q][1]==p);    ch[q][x]=ch[p][x^1];fa[ch[q][x]]=q;    ch[p][x^1]=q;fa[q]=p;    fa[p]=y;    if(y){        if(ch[y][0]==q) ch[y][0]=p;        else if(ch[y][1]==q) ch[y][1]=p;    } }inline void splay(int x){    for(int y;y=fa[x];rotate(x))        if(fa[y]) rotate((x==lc(y))==(y==lc(fa[y]))?y:x);    root=x;}inline void Ins(int x,int v){//插入    int y;    while(1){        y=ch[x][k[x]