题目大意:统计营业额。每天的统计的数字是今天的营业额和以前所有的营业额的最小差值。
思路:任何平衡树都可以。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define INF 10000000 using namespace std; struct Complex{ int random,val,cnt,size; Complex *son[2]; Complex() { random = rand(); cnt = size = 1; son[0] = son[1] = NULL; } void Maintain() { size = cnt; if(son[0] != NULL) size += son[0]->size; if(son[1] != NULL) size += son[1]->size; } int Compare(int x) { if(x == val) return -1; return x > val; } }*root; int cnt; inline void Rotate(Complex *&a,bool dir); void Insert(Complex *&a,int x); int FindPred(Complex *a,int x); int FindSucc(Complex *a,int x); int main() { int ans = 0; cin >> cnt; for(int x,i = 1;i <= cnt; ++i) { if(scanf("%d",&x) == EOF) x = 0; int pred = FindPred(root,x); int succ = FindSucc(root,x); Insert(root,x); if(i == 1) ans = x; else ans += min(x - pred,succ - x); } cout << ans << endl; return 0; } inline void Rotate(Complex *&a,bool dir) { Complex *k = a->son[!dir]; a->son[!dir] = k->son[dir]; k->son[dir] = a; a->Maintain(),k->Maintain(); a = k; } void Insert(Complex *&a,int x) { if(a == NULL) { a = new Complex(); a->val = x; return ; } int dir = a->Compare(x); if(dir == -1) a->cnt++; else { Insert(a->son[dir],x); if(a->son[dir]->random > a->random) Rotate(a,!dir); } a->Maintain(); } int FindPred(Complex *a,int x) { if(a == NULL) return -INF; if(a->val > x) return FindPred(a->son[0],x); return max(a->val,FindPred(a->son[1],x)); } int FindSucc(Complex *a,int x) { if(a == NULL) return INF; if(a->val < x) return FindSucc(a->son[1],x); return min(a->val,FindSucc(a->son[0],x)); }