題目鏈接：?http://www.lydsy.com/JudgeOnline/problem.php?id=1588

　　題目描述： 給你N個數(shù)， 定義f(i) 為第i個數(shù)與i個數(shù)絕對值的最小值， 求f(1) + f(2) + f(3) + ....... + f(n)

　　解題思路： 如何快速的找到與插入的值差的最小值， 就是左子樹的最大值與右子樹的最小值的絕對值差值的較小者。 一道平衡二叉樹的模板題， 自己也復(fù)習(xí)了一下數(shù)據(jù)結(jié)構(gòu)

　　代碼：?

/* *********************************************** Author :Kirisame_Marisa blog :http://www.cnblogs.com/KirisameMarisa/ Created Time :2015年03月24日 星期二 20時45分12秒 File Name :splay.cpp ************************************************ */#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> using namespace std; const int INF=0x3f3f3f3f; const int MAXN=100010; #define eps 1e-10 #define zero(x) (fabs(x)<eps) #define REP(X,N) for(int X=0;X<N;X++) #define REP2(X,L,R) for(int X=L;X<=R;X++) #define CLR(A,X) memset(A,X,sizeof(A)) #define PB(X) push_back(X) #define MP(X,Y) make_pair(X,Y) #define IT iterator #define test puts("OK") typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<PII> VII;const int null=-1;struct node {int par;int cld[2]; //0是左兒子，1是右兒子int key; } ts[MAXN]; int root,cnt;void init() {root=null;cnt=0; }int newnode(int p,int k) {ts[cnt].key=k;ts[cnt].par=p;ts[cnt].cld[0]=ts[cnt].cld[1]=null;return cnt++; }void rotate(int x,int k) //k=0為左旋，k=1為右旋 {int y=ts[x].par;ts[y].cld[!k]=ts[x].cld[k];if(ts[x].cld[k]!=null)ts[ts[x].cld[k]].par=y;ts[x].par=ts[y].par;if(ts[y].par!=null){if(y==ts[ts[y].par].cld[0])ts[ts[y].par].cld[0]=x;elsets[ts[y].par].cld[1]=x;}ts[y].par=x;ts[x].cld[k]=y; }void splay(int x,int S) //伸展操作，將x旋轉(zhuǎn)到目標(biāo)節(jié)點，其中S為目標(biāo)節(jié)點的parent {while(ts[x].par!=S){int p=ts[x].par;if(ts[p].par==S)rotate(x,ts[p].cld[0]==x);else{int d=(ts[ts[p].par].cld[0]==p);if(ts[p].cld[d]==x)rotate(x,!d),rotate(x,d);elserotate(p,d),rotate(x,d);}}if(S==-1)root=x; }bool insert(int x) {if(root==null){root=newnode(null,x);return 1;}int r=root,pre=null;while(r!=null){if(ts[r].key==x){splay(r,null); //如果直接找到的話就不新建節(jié)點，直接splayreturn 0;}else{pre=r;r=ts[r].cld[ts[r].key<x];}}int &t=ts[pre].cld[ts[pre].key<x];t=newnode(pre,x);splay(t,null);return 1; }int getlow(int x) //獲取比它小的最大值。由于插入操作x已經(jīng)被旋轉(zhuǎn)到根節(jié)點，所以只要尋找左子樹的最大值即可，下同 {int d=ts[root].cld[0];if(d==null)return INF;while(ts[d].cld[1]!=null)d=ts[d].cld[1];return x-ts[d].key; }int getup(int x) //獲取比它大的最小值 {int d=ts[root].cld[1];if(d==null)return INF;while(ts[d].cld[0]!=null)d=ts[d].cld[0];return ts[d].key-x; }void debug(int x) {int l=ts[x].cld[0],r=ts[x].cld[1];if(l!=null)debug(l);printf("id:%2d key:%2d par:%2d lcd:%2d rcd:%2d\n",x,ts[x].key,ts[x].par,l,r);if(r!=null)debug(r); }int main() {//freopen("in","r",stdin);//freopen("out","w",stdout); init();int n,x,sum=0;scanf("%d%d",&n,&x);sum+=x;insert(x);REP(i,n-1){x=0;scanf("%d",&x);bool temp=insert(x);if(temp)sum+=min(getlow(x),getup(x));}printf("%d\n",sum);return 0; } 模板

　　思考： 模板轉(zhuǎn)自http://www.cnblogs.com/KirisameMarisa/p/4366582.html， 感謝墨染之櫻花......另外自己也看了看這個splay , 都是很基礎(chǔ)的rotate和查詢， 就當(dāng)是回顧一下數(shù)據(jù)結(jié)構(gòu)

　　另外有一篇講的很好的平衡二叉樹文章， 放在這里， 提醒自己時刻進(jìn)行學(xué)習(xí).......前幾天發(fā)燒了， 是燒的真的嚴(yán)重....但是也看明白了一些事情， 學(xué)到了不少東西， 我要努力變強， 這個學(xué)校我一分鐘也不想待在這里！

轉(zhuǎn)載于:https://www.cnblogs.com/FriskyPuppy/p/7545158.html

總結(jié)

以上是生活随笔為你收集整理的HYSBZ 1588 营业额统计 平衡二叉树模板的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。