本文共 2699 字，大约阅读时间需要 8 分钟。

题意:给你n个数,要你求出每个数的最小波动值之和.第一个数的波动值就是自己,之后第i个数的最小波动值=|val[i]-x|.其中x是与val[i]之差绝对值最小的之前出现过的数.

分析:

构建一个SplayTree,支持插入节点,找前驱和后继的值.当然还要支持单点插入操作,不过这颗SplayTree是一个排序二叉树,即关键字从小到大排序,这样才能找到前驱和后继.

#include
   
    using namespace std;const int maxn = 1e5+99;const int INF = 0x3f3f3f3f;struct spalytree{    int ch[maxn][2],pre[maxn],sz[maxn],key[maxn],root,tot1;    void Rotate(int x,int d)    {        int y = pre[x];        ch[y][!d] = ch[x][d];        pre[ch[x][d]]=y;        if(pre[y])ch[pre[y]][ch[pre[y]][1]==y] = x;        pre[x] = pre[y];        ch[x][d] = y;        pre[y] = x;    }    void splay(int r,int goal)    {        while(pre[r]!=goal)        {            if(pre[pre[r]] == goal)                Rotate(r,ch[pre[r]][0] ==r);            else            {                int y =  pre[r];                int d = ch[pre[y]][0] ==y;                if(ch[y][d] == r)                {                    Rotate(r,!d);                    Rotate(r,d);                }                else                {                    Rotate(y,d);                    Rotate(r,d);                }            }        }        if(goal == 0) root = r;    }    void newnode(int &r,int fa,int k)    {        r = ++tot1;        sz[r] = 1;//不需要        key[r] = k;        pre[r] = fa;        ch[r][0] = ch[r][1] = 0;    }    /**建立排序树*/    int insert(int k)/**插入一个值为k的节点，insert一个一个的写*/    {        int r = root;        while(1)        {            if(key[r]==k)            {                splay(r,0);                return 0;            }            else if(k
    
     key[r])            {                if(ch[r][1])r=ch[r][1];                else                {                    newnode(ch[r][1],r,k);                    splay(ch[r][1],0);                    return 1;                }            }        }    }       /**找前面出现的最接近这个值的，从比他大的找最小的，从比他小的找最大的，然后去判断这两个值哪个更接近他*/    int get_pre(int x)    {        int r = ch[x][0];        if(r==0)return INF;        while(ch[r][1])r = ch[r][1];        return key[x] - key[r];    }    int get_next(int x)    {        int r = ch[x][1];        if(r==0)return INF;        while(ch[r][0])r = ch[r][0];        return key[r]-key[x];    }}st;int main(){    int n;    while(scanf("%d",&n)==1)    {        st.root = st.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;                st.newnode(st.root,0,num);                continue;            }            if(st.insert(num)==0)continue;            int a = st.get_pre(st.root);            int b = st.get_next(st.root);            ans += min(a,b);        }        printf("%d\n",ans);    }}
    
   

转载地址：http://cbyci.baihongyu.com/