题目链接：http://www.wikioi.com/problem/1296/
算法：Splay
这是非常经典的一道题目，用Splay树来维护营业额，每天的最小波动值就等于 min{树根-树根的前驱, 树根的后继-树根)
所以用Splay来维护
PS: 本题数据有问题，所以当空行时，值为0
代码：
|
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
|
#include <cstdio>using
namespace
std;
#define F(rt) rt-> pa#define K(rt) rt-> key#define CH(rt, d) rt-> ch[d]#define C(rt, d) (K(rt) > d ? 0 : 1)#define NEW(d) new Splay(d)#define PRE(rt) F(rt) = CH(rt, 0) = CH(rt, 1) = nullint
n, ans;
struct
Splay {
Splay* ch[2], *pa;
int
key;
Splay(int
d = 0) : key(d) { ch[0] = ch[1] = pa = NULL; }
};typedef
Splay* tree;
tree null = new
Splay, root = null;
void
rot(tree& rt, int
d) {
tree k = CH(rt, d^1), u = F(rt); int
flag = CH(u, 1) == rt;
CH(rt, d^1) = CH(k, d); if(CH(k, d) != null) F(CH(k, d)) = rt;
CH(k, d) = rt; F(rt) = k; rt = k; F(rt) = u;
if(u != null) CH(u, flag) = k;
}void
splay(tree nod, tree& rt) {
if(nod == null) return;
tree pa = F(rt);
while(F(nod) != pa) {
if(F(nod) == rt)
rot(rt, CH(rt, 0) == nod);
else
{
int
d = CH(F(F(nod)), 0) == F(nod);
int
d2 = CH(F(nod), 0) == nod;
if(d == d2) { rot(F(F(nod)), d); rot(F(nod), d2); }
else
{ rot(F(nod), d2); rot(F(nod), d); }
}
}
rt = nod;
}tree maxmin(tree rt, int
d) {
if(rt == null) return
null;
while(CH(rt, d) != null) rt = CH(rt, d);
return
rt;
}tree ps(tree rt, int
d) {
if(rt == null) return
null;
rt = CH(rt, d);
return
maxmin(rt, d^1);
}tree search(tree& rt, int
d) {
tree t = rt;
while(t != null && K(t) != d) t = CH(t, C(t, d));
splay(t, rt);
return
t;
}void
insert(tree& rt, int
d) {
tree q = NULL, t = rt;
while(t != null) q = t, t = CH(t, C(t, d));
t = NEW(d);
PRE(t);
if(q) F(t) = q, CH(q, C(q, d)) = t;
else
rt = t;
splay(t, rt);
}void
del(tree& rt) {
if(rt == null) return;
tree t = rt;
if(CH(t, 0) == null) t = CH(rt, 1);
else
{
t = CH(rt, 0);
splay(maxmin(t, 1), t);
CH(t, 1) = CH(rt, 1);
if(CH(rt, 1) != null) F(CH(rt, 1)) = t;
}
delete
rt;
F(t) = null;
rt = t;
}void
init(int
key) {
if(root == null) { root = NEW(key); PRE(root); ans += key; return; }
insert(root, key);
tree succ = ps(root, 0), pred = ps(root, 1);
if(succ == null) { ans += K(pred) - K(root); splay(pred, root); return; }
if(pred == null) { ans += K(root) - K(succ); splay(succ, root); return; }
int
l = K(root) - K(succ), r = K(pred) - K(root);
if(l <= r) { ans += l; splay(succ, root); }
else
{ ans += r; splay(pred, root); }
}int
main() {
PRE(null);
scanf("%d", &n);
int
c;
for(int
i = 0; i < n; ++i) { if(scanf("%d", &c) == EOF) c = 0; init(c); } //坑爹的读入
printf("%d\n", ans);
return
0;
} |