题意：给出一个公司每一天的营业额，求每天的最小波动值之和。该天的最小波动值= min { 绝对值| 该天以前某一天的营业额-该天的营业额 | }。第一天的最小波动值就是其自己。
思路：Splay伸展树的入门题，仅有splay，insert，rotate这三个主要的函数而已。
将一个数字（营业额）插入树中，并把其splay到根位置，然后其前驱和后继中离它较近的一个用来求最小波动值。注意可能没有前驱/后继。对第一个数特别处理。
注意：此题的数据有缺陷，读入营业额之前先将变量清零。
#include <bits/stdc++.h>
#define pii pair<int,int>
#define INF 0x7f7f7f7f
#define LL long long
using namespace std;
const int N=;
int root, node_cnt;
struct node
{
int pre, val, ch[];
}nod[N]; int create_node(int v,int far) //返回节点下标
{
nod[node_cnt].val=v;
nod[node_cnt].pre=far;
nod[node_cnt].ch[]=;
nod[node_cnt].ch[]=;
return node_cnt++;
} void Rotate(int t, int d) //d为方向,0是左旋，1是右
{
int far=nod[t].pre;
int son=nod[t].ch[d]; //far的孩子
int gra=nod[far].pre; //far的父亲 nod[son].pre=far;
nod[t].pre=gra;
nod[far].pre=t; nod[far].ch[d^]=son;
nod[t].ch[d]=far;
nod[gra].ch[nod[gra].ch[]==far]=t;
} void Splay(int t,int goal) //将t转为goal的任一孩子
{
while( nod[t].pre!=goal ) //t还不是根
{
int f=nod[t].pre, g=nod[f].pre;
if( g==goal ) Rotate( t, nod[f].ch[]==t ); //父亲就是根s，旋1次
else
{
int d1=(nod[f].ch[]==t), d2=(nod[g].ch[]==f);
if( d1==d2 ) //两次同向旋转
{
Rotate( f, d1);
Rotate( t, d1);
}
else //两次反向旋转
{
Rotate( t, d1);
Rotate( t, d2);
}
}
}
if(!goal) root=t; //时刻更新树根
} int Insert(int t, int v)
{
if(v==nod[t].val) return -;
int q=-;
if( v>nod[t].val ) //右边
{
if( nod[t].ch[]== ) q=(nod[t].ch[]=create_node(v, t));
else q=Insert(nod[t].ch[], v);
}
else //左边
{
if( nod[t].ch[]== ) q=(nod[t].ch[]=create_node(v, t));
else q=Insert(nod[t].ch[], v);
}
return q;
}
int get_pre(int t, int d) //求前驱和后继的，d=1代表求前驱
{
if(nod[t].ch[d]) return get_pre(nod[t].ch[d], d);
return nod[t].val;
} void init()
{
root=node_cnt=;
create_node(INF,); //0号点是不要的
}
int main()
{
freopen("input.txt", "r", stdin);
int n;
while(cin>>n)
{
init();
int ans=;
for(int i=,a=; i<n; i++,a=)
{
scanf("%d", &a);
int t=Insert(root, a);
if(t<) continue; //已经存在此数字
Splay(t, ); //将t伸展一下到根
if(i==) ans=a; //第一个数字
else if( nod[t].ch[] && nod[t].ch[] )
ans+=min( abs(a-get_pre(nod[t].ch[], )), abs(a-get_pre( nod[t].ch[], )));
else if( nod[t].ch[] ) ans+=abs( a-get_pre( nod[t].ch[], ) );
else if( nod[t].ch[] ) ans+=abs( a-get_pre( nod[t].ch[], ) ); }
cout<<ans<<endl;
}
return ;
}
AC代码