首页 > 代码库 > bzoj 1588 平衡树 splay
bzoj 1588 平衡树 splay
1588: [HNOI2002]营业额统计
Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 15446 Solved: 6076
[Submit][Status][Discuss]
Description
营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况： 该天的最小波动值 当最小波动值越大时，就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。 ? 输入输出要求
Input
第一行为正整数 ，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数(有可能有负数) ，表示第i
天公司的营业额。
天数n<=32767,
每天的营业额ai <= 1,000,000。
最后结果T<=2^31
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
该题数据bug已修复.----2016.5.15
题意：每次插入一个数，在数列中找到一个数，使得该数与插入的数的差值最小 差值取绝对值 求和输出
题解：平衡树入门 通过旋转 在不影响树的结构的情况下 保持最优的操作效率 splay
1 #include <bits/stdc++.h> 2 #define ll long 3 using namespace std; 4 ll tim=0,n,root,sum=0; 5 bool flag; 6 struct node 7 { 8 ll father,left,right,data; 9 } tree[100005]; 10 ll mins(ll aaa, ll bbb) 11 { 12 if(aaa<bbb) 13 return aaa; 14 else 15 return bbb; 16 } 17 ll abss(ll x) 18 { 19 if(x<0) 20 return -x; 21 else 22 return x; 23 } 24 void rightrotate(ll x) 25 { 26 ll y=tree[x].father; 27 ll z=tree[y].father; 28 tree[y].left=tree[x].right; 29 if(tree[x].right!=-1) 30 { 31 tree[tree[x].right].father=y; 32 } 33 tree[x].father=z; 34 if(z!=-1) 35 { 36 if(tree[z].left==y) tree[z].left=x; 37 else tree[z].right=x; 38 } 39 tree[x].right=y; 40 tree[y].father=x; 41 } 42 void leftrotate(ll x) 43 { 44 ll y=tree[x].father; 45 ll z=tree[y].father; 46 tree[y].right=tree[x].left; 47 if(tree[x].left!=-1) 48 { 49 tree[tree[x].left].father=y; 50 } 51 tree[x].father=z; 52 if(z!=-1) 53 { 54 if(tree[z].left==y) tree[z].left=x; 55 else tree[z].right=x; 56 } 57 tree[x].left=y; 58 tree[y].father=x; 59 } 60 void splay(ll x) 61 { 62 while(tree[x].father!=-1) 63 { 64 ll y=tree[x].father; 65 ll z=tree[y].father; 66 if(z==-1) 67 { 68 if(tree[y].left==x) rightrotate(x); 69 else leftrotate(x); 70 } 71 else 72 { 73 if(tree[z].left==y&&tree[y].left==x) 74 { 75 rightrotate(y); 76 rightrotate(x); 77 } 78 else if(tree[z].left==y&&tree[y].right==x) 79 { 80 leftrotate(x); 81 rightrotate(x); 82 } 83 else if(tree[z].right==y&&tree[y].right==x) 84 { 85 leftrotate(y); 86 leftrotate(x); 87 } 88 else 89 { 90 rightrotate(x); 91 leftrotate(x); 92 } 93 } 94 }root=x; 95 } 96 ll qq(ll x) 97 { 98 ll y=tree[x].left; 99 if(y==-1) return y;100 while(tree[y].right!=-1) y=tree[y].right;101 return y;102 }103 ll hj(ll x)104 {105 ll y=tree[x].right;106 if(y==-1) return y;107 while(tree[y].left!=-1) y=tree[y].left;108 return y;109 }110 int BST_insert(ll dat,ll x)111 {112 if(dat==tree[x].data)113 {114 flag=false ;115 splay(x);116 return 0;117 }118 if(dat<tree[x].data)119 {120 if(tree[x].left==-1)121 {122 tree[x].left=tim;123 tree[tim].father=x;124 tree[tim].left=tree[tim].right=-1;125 tree[tim].data=http://www.mamicode.com/dat;126 }127 else128 BST_insert(dat,tree[x].left);129 }130 else131 {132 if(tree[x].right==-1)133 {134 tree[x].right=tim;135 tree[tim].father=x;136 tree[tim].left=tree[tim].right=-1;137 tree[tim].data=http://www.mamicode.com/dat;138 }139 else140 BST_insert(dat,tree[x].right);141 }142 }143 ll insert1(ll dat)144 {145 flag=true;146 tim++;147 BST_insert(dat,root);148 if(flag==false) return 0;149 splay(tim);150 ll q=qq(tim);151 ll h=hj(tim);152 ll minx=2000000000;153 if(q!=-1) minx=mins(minx,abss(tree[q].data-dat));154 if(h!=-1) minx=mins(minx,abss(tree[h].data-dat));155 sum+=minx;156 }157 int main()158 {159 int n;160 ll aa=0;161 while(scanf("%d",&n)!=-1)162 {163 sum=0;164 tim=0;165 scanf("%ld",&aa);166 sum=aa;167 tim++;168 tree[tim].father=-1;169 tree[tim].left=tree[tim].right=-1;170 tree[tim].data=http://www.mamicode.com/aa;171 root=tim;172 for(ll i=1; i<n; i++)173 {174 aa=0;175 scanf("%ld",&aa);176 insert1(aa);177 }178 printf("%ld\n",sum);179 }180 return 0;181 }
bzoj 1588 平衡树 splay
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。