n天
n个营业额;
sum(min(abs(wi-前面)));
splay维护一下就可以
#include<stdio.h>
#include<algorithm>
#include<math.h> using namespace std;
#define inf 2000000000
int sum,time,flag,root; struct node
{
int fa,l,r,w;
}tree[];
void rightrotate(int x) //右旋
{
int y=tree[x].fa;
int z=tree[y].fa;
tree[y].l=tree[x].r;
if(tree[x].r!=-)
tree[tree[x].r].fa=y;
tree[x].fa=z;
if(z!=-)
{
if(tree[z].l==y)
tree[z].l=x;
else
tree[z].r=x;
}
tree[x].r=y;
tree[y].fa=x;
}
void leftrotate(int x)//左旋
{
int y=tree[x].fa;
int z=tree[y].fa;
tree[y].r=tree[x].l;
if(tree[x].l!=-)
tree[tree[x].l].fa=y;
tree[x].fa=z;
if(z!=-)
{
if(tree[z].l==y)
tree[z].l=x;
else
tree[z].r=x;
}
tree[x].l=y;
tree[y].fa=x;
}
void splay(int x)
{
while(tree[x].fa!=-)
{
int y=tree[x].fa;
int z=tree[y].fa;
if(z==-) //6种旋转情况
{
if(tree[y].l==x)
rightrotate(x);
else
leftrotate(x);
}
else
{
if(tree[z].l==y&&tree[y].l==x)
{
rightrotate(y);
rightrotate(x);
}
else if(tree[z].l==y&&tree[y].r==x)
{
leftrotate(x);
rightrotate(x);
}
else if(tree[z].r==y&&tree[y].r==x)
{
leftrotate(y);
leftrotate(x);
}
else
{
rightrotate(x);
leftrotate(x);
}
}
}
root=x;
}
void BST_insert(int w,int x) //插入 就和二叉排序树一样
{
if(w==tree[x].w)
{
flag=false;
splay(x);
return ;
}
else if(w<tree[x].w)
{
if(tree[x].l==-)
{
tree[x].l=time;
tree[time].fa=x;
tree[time].l=tree[time].r=-;
tree[time].w=w;
}
else
BST_insert(w,tree[x].l);
}
else
{
if(tree[x].r==-)
{
tree[x].r=time;
tree[time].fa=x;
tree[time].l=tree[time].r=-;
tree[time].w=w;
}
else
BST_insert(w,tree[x].r);
}
}
int f_pr(int x) //前面最大
{
int y=tree[x].l;
if(y==-)
return y;
while(tree[y].r!=-)
y=tree[y].r;
return y;
}
int f_ne(int x) //后面最小
{
int y=tree[x].r;
if(y==-)
return y;
while(tree[y].l!=-)
y=tree[y].l;
return y;
}
void Insert(int w)
{
flag=true;
time++;
BST_insert(w,root);
if(flag==false)
return ;
splay(time);
int q=f_pr(time);
int p=f_ne(time);
int mi=inf;
if(q!=-)
mi=min(mi,abs(tree[q].w-w));
if(p!=-)
mi=min(mi,abs(tree[p].w-w));
sum+=mi;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
scanf("%d",&sum);
time=;
tree[time].fa=tree[time].l=tree[time].r=-;
tree[time].w=sum;
root=time;
for(int i=;i<n;i++)
{
int a;
scanf("%d",&a);
Insert(a);
}
printf("%d\n",sum);
}
return ;
}