营业额统计问题的三种巧妙解法
问题的简短描述：
给出n天的营业额，该天的最小波动值=min{|该天以前某一天的营业额-该天的营业额|} 。第一天的最小波动值为第一天的营业额。求n天的最小波动值之和。n<=32767，营业额a<= 1000000。详见：http://new.tyvj.cn/Problem_Show.aspx?id=1185
样例输入：
6 5 1 2 5 4 6
样例输出：
12
样例解释：
5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12
巧解一：
A[i]表示第i天的营业额。到了第i天时，设前面与A[i]最接近的营业额为m。考察样例可以知道，m出现多少次并不重要。例如在样例的第5天，前面的日子里和第5天的营业额最接近的为营业额4，而营业额4出现了两次。这启发我们，在第5天的时候，只用知道前面都出现过哪些营业额即可，并不用记录他们出现的次数。于是巧妙的算法诞生了——
int s=0;
while(!A[x-s] && !A[x+s]) s++;//第i天的营业额为x，往两头找。
ans+=s;
A[x]=true;
这里的A[i]表示为营业额i是否出现过的标志。
可还是一个一个查找啊？！算法不会快。评测系统答道：我给你的算法跪了，恭喜你，你的程序运行时间为0ms，请接受自动生成的祝贺[1]。
想想对于这样的算法，最强悍的数据是怎样的。可以用二分思想得到这样的数据。每次选择中间的营业额。
加法的次数=2(len+len/2+len/4+len/8+len/16……len/2^k)=2len(2-1/2k)=4len，而len为营业额可能的最大值，即len=1000000。故算法复杂度为O(4len)。
#include<cstdio>#include<cstring>#include<math.h>#include<stdlib.h>#include<algorithm>#include<ctime>#include<iostream>#define INF 1<<30using namespace std;const int maxn=32768;struct Tnode{Tnode *c[2];int v,size;void CalSize(){size=c[0]->size+c[1]->size+1;}Tnode (int _v,int _size,Tnode *_c){v=_v;size=_size;c[0]=c[1]=_c;}Tnode (){}}node[maxn],TNull(0,0,0),*Null=&TNull;int cnt=0;Tnode *NewNode(){Tnode *u=&node[cnt++];u->c[0]=u->c[1]=Null;u->size=1;return u;}void rot(Tnode *&u,bool d){Tnode *p=u->c[d];u->c[d]=p->c[!d];p->c[!d]=u;p->CalSize();u->CalSize();u=p;}void maintain(Tnode *&u,bool d){if(u==Null) return;Tnode *&p=u->c[d];if(p->c[d]->size>u->c[!d]->size)rot(u,d); else if(p->c[!d]->size >u->c[!d]->size) { rot(p,!d); rot(u,d); }else return; maintain(u->c[0],0); maintain(u->c[1],1); maintain(u,0); maintain(u,1);}void insert(Tnode*&u,int v){if(u==Null){u=NewNode();u->v=v;return;}if(v==u->v) return;bool d=v>u->v;insert(u->c[d],v);maintain(u,d);u->CalSize();}int findClose(Tnode *u,int v){if(u==Null) return INF;if(u->v==v) return 0;int d=v>u->v;int p=findClose(u->c[d],v);return min(p,abs(u->v-v));}void printTree(Tnode *u){if(u==Null) return;printf("%d\n",u->v);for(int i=0;i<1;i++) printTree(u->c[i]);}int main(){#ifndef ONLINE_JUDGE freopen("in.txt","r",stdin);#endifint i,j;int n;scanf("%d",&n);int x;scanf("%d",&x);int ans=x;Tnode *root=Null;insert(root,x);Null->c[0]=Null->c[1]=Null;//necessary//printf("%d\n",NULL);//printf("%d\n",root->v);//printTree(root);for(i=1;i<n;i++){scanf("%d",&x);ans+=findClose(root,x);//printf("%d\n",ans);insert(root,x);//printTree(root);}printf("%d\n",ans);//rintTree(root);//printf("ok\n");//printf("%.2lf\n",(double)clock()/CLOCKS_PER_SEC); return 0;}/**/注释：
[1]我很喜欢usaco。它的自动祝贺一定让很多oiers乐了。
参考：
1、陈启峰《Size Balanced Tree》
2、刘汝佳《基础数据结构》
3、WJMZBMR的SBT c++ code。http://www.nocow.cn/index.php/Code:SBT_C%2B%2B