splay HYSBZ1588

n天
n个营业额;
sum(min(abs(wi-前面)));
splay维护一下就可以
  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<math.h>
  4 
  5 using namespace std;
  6 #define inf 2000000000
  7 int sum,time,flag,root;
  8 
  9 struct node
 10 {
 11     int fa,l,r,w;
 12 }tree[100010];
 13 void rightrotate(int x) //右旋
 14 {
 15     int y=tree[x].fa;
 16     int z=tree[y].fa;
 17     tree[y].l=tree[x].r;
 18     if(tree[x].r!=-1)
 19         tree[tree[x].r].fa=y;
 20     tree[x].fa=z;
 21     if(z!=-1)
 22     {
 23         if(tree[z].l==y)
 24             tree[z].l=x;
 25         else
 26             tree[z].r=x;
 27     }
 28     tree[x].r=y;
 29     tree[y].fa=x;
 30 }
 31 void leftrotate(int x)//左旋
 32 {
 33     int y=tree[x].fa;
 34     int z=tree[y].fa;
 35     tree[y].r=tree[x].l;
 36     if(tree[x].l!=-1)
 37         tree[tree[x].l].fa=y;
 38     tree[x].fa=z;
 39     if(z!=-1)
 40     {
 41         if(tree[z].l==y)
 42             tree[z].l=x;
 43         else
 44             tree[z].r=x;
 45     }
 46     tree[x].l=y;
 47     tree[y].fa=x;
 48 }
 49 void splay(int x)
 50 {
 51     while(tree[x].fa!=-1)
 52     {
 53          int y=tree[x].fa;
 54          int z=tree[y].fa;
 55          if(z==-1)                  //6种旋转情况
 56          {
 57              if(tree[y].l==x)
 58                 rightrotate(x);
 59              else
 60                 leftrotate(x);
 61          }
 62          else
 63          {
 64              if(tree[z].l==y&&tree[y].l==x)
 65              {
 66                  rightrotate(y);
 67                  rightrotate(x);
 68              }
 69              else if(tree[z].l==y&&tree[y].r==x)
 70              {
 71                  leftrotate(x);
 72                  rightrotate(x);
 73              }
 74              else if(tree[z].r==y&&tree[y].r==x)
 75              {
 76                  leftrotate(y);
 77                  leftrotate(x);
 78              }
 79              else
 80              {
 81                  rightrotate(x);
 82                  leftrotate(x);
 83              }
 84          }
 85     }
 86     root=x;
 87 }
 88 void BST_insert(int w,int x)  //插入  就和二叉排序树一样
 89 {
 90     if(w==tree[x].w)
 91     {
 92         flag=false;
 93         splay(x);
 94         return ;
 95     }
 96     else if(w<tree[x].w)
 97     {
 98         if(tree[x].l==-1)
 99         {
100             tree[x].l=time;
101             tree[time].fa=x;
102             tree[time].l=tree[time].r=-1;
103             tree[time].w=w;
104         }
105         else
106             BST_insert(w,tree[x].l);
107     }
108     else
109     {
110         if(tree[x].r==-1)
111         {
112             tree[x].r=time;
113             tree[time].fa=x;
114             tree[time].l=tree[time].r=-1;
115             tree[time].w=w;
116         }
117         else
118             BST_insert(w,tree[x].r);
119     }
120 }
121 int f_pr(int x)  //前面最大
122 {
123     int y=tree[x].l;
124     if(y==-1)
125         return y;
126     while(tree[y].r!=-1)
127         y=tree[y].r;
128     return y;
129 }
130 int f_ne(int x) //后面最小
131 {
132     int y=tree[x].r;
133     if(y==-1)
134         return y;
135     while(tree[y].l!=-1)
136         y=tree[y].l;
137     return y;
138 }
139 void Insert(int w)
140 {
141     flag=true;
142     time++;
143     BST_insert(w,root);
144     if(flag==false)
145         return ;
146     splay(time);
147     int q=f_pr(time);
148     int p=f_ne(time);
149     int mi=inf;
150     if(q!=-1)
151         mi=min(mi,abs(tree[q].w-w));
152     if(p!=-1)
153         mi=min(mi,abs(tree[p].w-w));
154     sum+=mi;
155 }
156 int main()
157 {
158     int n;
159     while(scanf("%d",&n)!=EOF)
160     {
161             scanf("%d",&sum);
162             time=1;
163             tree[time].fa=tree[time].l=tree[time].r=-1;
164             tree[time].w=sum;
165             root=time;
166             for(int i=1;i<n;i++)
167             {
168                 int a;
169                 scanf("%d",&a);
170                 Insert(a);
171             }
172             printf("%d
",sum);
173     }
174     return 0;
175 }