1588: [HNOI2002]营业额统计

Description
营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：该天的最小波动值当最小波动值越大时，就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。第一天的最小波动值为第一天的营业额。  输入输出要求
Input
第一行为正整数，表示该公司从成立一直到现在的天数，接下来的n行每行有一个正整数，表示第i天公司的营业额。
Output
输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。
Sample Input
6
5
1
2
5
4
6
Sample Output
12
HINT

结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

splay裸题，所以试了一下自顶向下，感觉好写一点，但是我不会写双旋，而且插入也是乱搞的，所以时间就长了一点，不过还是能过的

  1 const
  2     maxn=33000;
  3 type
  4     node=record
  5       son:array[0..1]of longint;
  6       data:longint;
  7     end;
  8 var
  9     tree:array[0..maxn]of node;
 10     root,n,tot:longint;
 11     ans:int64;
 12 
 13 procedure down(var x:longint;y:longint);
 14 begin
 15     if x>y then x:=y;
 16 end;
 17 
 18 procedure splay(x:longint;var root:longint);
 19 var
 20     tmp:longint;
 21 begin
 22     if tree[root].data=x then exit;
 23     if x<tree[root].data then
 24       begin
 25         if tree[root].son[0]=0 then exit;
 26         splay(x,tree[root].son[0]);
 27         tmp:=tree[root].son[0];
 28         tree[root].son[0]:=tree[tmp].son[1];
 29         tree[tmp].son[1]:=root;
 30         root:=tmp;
 31       end
 32     else
 33       begin
 34         if tree[root].son[1]=0 then exit;
 35         splay(x,tree[root].son[1]);
 36         tmp:=tree[root].son[1];
 37         tree[root].son[1]:=tree[tmp].son[0];
 38         tree[tmp].son[0]:=root;
 39         root:=tmp;
 40       end;
 41 end;
 42 
 43 function pre:longint;
 44 begin
 45     pre:=tree[root].son[0];
 46     while tree[pre].son[1]<>0 do
 47       pre:=tree[pre].son[1];
 48 end;
 49 
 50 function succ:longint;
 51 begin
 52     succ:=tree[root].son[1];
 53     while tree[succ].son[0]<>0 do
 54       succ:=tree[succ].son[0];
 55 end;
 56 
 57 procedure insert(x:longint);
 58 var
 59     aug:longint;
 60 begin
 61     splay(x,root);
 62     if tree[root].data=x then exit;
 63     inc(tot);
 64     tree[tot].data:=x;
 65     if x<tree[root].data then
 66       begin
 67         aug:=tree[root].data-x;
 68         if tree[root].son[0]<>0 then down(aug,x-tree[pre].data);
 69         tree[tot].son[0]:=tree[root].son[0];
 70         tree[root].son[0]:=tot;
 71       end
 72     else
 73       begin
 74         aug:=x-tree[root].data;
 75         if tree[root].son[1]<>0 then down(aug,tree[succ].data-x);
 76         tree[tot].son[1]:=tree[root].son[1];
 77         tree[root].son[1]:=tot;
 78       end;
 79     ans:=ans+aug;
 80 end;
 81 
 82 procedure main;
 83 var
 84     i,x:longint;
 85 begin
 86     read(n);
 87     root:=1;
 88     tot:=1;
 89     read(tree[1].data);
 90     ans:=abs(tree[1].data);
 91     for i:=2 to n do
 92       begin
 93         read(x);
 94         insert(x);
 95       end;
 96     write(ans);
 97 end;
 98 
 99 begin
100     main;
101 end.

View Code