BZOJ1588: [HNOI2002]营业额统计
Description
营 业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业 额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了 一种最小波动值来衡量这种情况： 该天的最小波动值 当最小波动值越大时，就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。
Input
第一行为正整数 ，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数(有可能有负数) ，表示第i天公司的营业额。
Output
输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。
Sample Input
6
5
1
2
5
4
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
【分析见下，先奉上代码】
program turnover;
type
tnode=record
father,left,right:integer;
data:longint;
end;
var
tree:array[0..32800] of tnode;
root,now1,now,min,next,prev,n:longint;
ans:int64;
procedure leftrotate(x:integer);
var
y:integer;
begin
y:=tree[x].father;
tree[y].right:=tree[x].left;
if tree[x].left <> 0 then
tree[tree[x].left].father:=y;
tree[x].father:=tree[y].father;
if tree[y].father<>0 then
begin
if y=tree[tree[y].father].left
then tree[tree[y].father].left:=x
else tree[tree[y].father].right:=x;
end;
tree[y].father:=x;
tree[x].left:=y;
end;
procedure rightrotate(x:integer);
var
y:integer;
begin
y:=tree[x].father;
tree[y].left:=tree[x].right;
if tree[x].right <> 0 then
tree[tree[x].right].father:=y;
tree[x].father:=tree[y].father;
if tree[y].father<>0 then
begin
if y=tree[tree[y].father].left
then tree[tree[y].father].left:=x
else tree[tree[y].father].right:=x;
end;
tree[y].father:=x;
tree[x].right:=y;
end;
procedure splay(now:integer);
var
t:integer;
begin
while tree[now].father<>0 do
begin
t:=tree[now].father;
if tree[t].father=0 then
begin
if now=tree[t].left
then {zig} rightrotate(now)
else {zag} leftrotate(now);
break;
end;
if now=tree[t].left
then begin
if t=tree[tree[t].father].left
then begin
rightrotate(t);
rightrotate(now);
end
else begin
rightrotate(now);
leftrotate(now);
end
end
else begin
if t=tree[tree[t].father].right
then begin
leftrotate(t);
leftrotate(now);
end
else begin //zag zig
leftrotate(now);
rightrotate(now);
end
end;
end;
root:=now;
end;
procedure ins();
var
t:integer;
begin
t:=root;
now1:=now;
while true do
begin
if (tree[now].data=tree[t].data)then
begin
now1:=t;
min:=0;
exit;
end;
if (tree[t].data>tree[now].data)
then begin
if tree[t].left=0
then begin
tree[now].father:=t;
tree[t].left:=now;
exit;
end
else t:=tree[t].left;
end
else begin
if tree[t].right=0
then begin
tree[now].father:=t;
tree[t].right:=now;
exit;
end
else t:=tree[t].right;
end;
end;
end;
procedure findprev;
begin
prev:=tree[now].left;
while prev<>0 do
begin
if tree[prev].right=0 then exit;
prev:=tree[prev].right;
end;
end;
procedure findnext;
begin
next:=tree[now].right;
while next<>0 do
begin
if tree[next].left=0 then exit;
next:=tree[next].left;
end;
end;
procedure work();
begin
readln(tree[now].data);
min:=maxint;
ins();
splay(now1);
if min>0 then
begin
findprev;
findnext;
if (next<>0)and((prev=0)or
(tree[next].data-tree[now].data<tree[now].data-tree[prev].data))
then min:=tree[next].data-tree[now].data
else min:=tree[now].data-tree[prev].data;
end;
ans:=ans+min;
end;
begin
fillchar(tree,sizeof(tree),0);
readln(n);
now:=1;
readln(tree[1].data);
root:=1;
ans:=tree[1].data;
for now:=2 to n do
work;
writeln(ans);
end.
|
RunID |
User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 908799 | Chuck__ | 1588 | Accepted | 612 kb | 232 ms | Pascal/Edit | 4181 B | 2015-03-27 22:20:34 |
4k+的代码量有点大了。明天缩一缩，顺便再用线段树AC一次，在写个splay tree的详细内容
我来写下题目的【分析】。
首先，这题是标准的SPLAY TREE模板题。
我今天花了一节体育课一节微机课和45分钟的睡觉时间搞定了splay tree
它算是一种二叉排序树，重点的操作在zig.zag上（zig zag到底是什么鬼单词！）
zig是右旋
zag是左旋
旋转的目的是为了把目标结点转换成根。这样就方便查找了。
如题，查找的内容是最小差值，
那么我们已知根（目前操作的数）
再从左子树里（比目前操作数要小的）中间找出最大的prev
从右子树里（比目前操作数要大的）中间找出最小的next。
再判断最小的差值min(now.data-prev.data,next.data-now.data)
操作完之后再插入时维护左边小右边大就行了。
语文差，勿吐槽。
我来写下题目的【分析】。
首先，这题是标准的SPLAY TREE模板题。
它算是一种二叉排序树，重点的操作在zig.zag上
zig是右旋
zag是左旋
旋转的目的是为了把目标结点转换成根。这样就方便查找了。
如题，查找的内容是最小差值，
那么我们已知根（目前操作的数）
再从左子树里（比目前操作数要小的）中间找出最大的prev
从右子树里（比目前操作数要大的）中间找出最小的next。
再判断最小的差值min(now.data-prev.data,next.data-now.data)
操作完之后再插入时维护左边小右边大就行了。
语文差，勿吐槽。
评论 (0)
