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
【分析见下，先奉上代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 | 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)
