Tiger最近被公司升任為營業(yè)部經(jīng)理，他上任后接受公司交給的第一項任務(wù)便是統(tǒng)計并分析公司成立以來的營業(yè)情況。 Tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業(yè)額。分析營業(yè)情況是一項相當復雜的工作。由于節(jié)假日，大減價或者是其他情況的時候，營業(yè)額會出現(xiàn)一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業(yè)額突變得很高或是很低，這就證明公司此時的經(jīng)營狀況出現(xiàn)了問題。經(jīng)濟管理學上定義了一種最小波動值來衡量這種情況：
第一行為正整數(shù) ，表示該公司從成立一直到現(xiàn)在的天數(shù)，接下來的n行每行有一個整數(shù)(有可能有負數(shù)) ，表示第i天公司的營業(yè)額。
輸出文件僅有一個正整數(shù)，即Sigma(每天最小的波動值) 。結(jié)果小于2^31 。
6 5 1 2 5 4 6
12
結(jié)果說明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12
在splay中查找前驅(qū)和后繼即可。
#include<cmath>#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int N = 33000, inf = 1 << 30;struct Splay{ int a; Splay *c[2], *f; int d(){return f->c[1] == this;} void sc(Splay* x, int d){(c[d] = x)->f = this;}};Splay *null = new Splay();Splay *root = new Splay();void rotate(Splay *x){ int d = x->d(); Splay* p = x->f; p->sc(x->c[!d], d); if(p == root) x->f = null, root = x; else p->f->sc(x, p->d()); x->sc(p, !d);}void splay(Splay *x){ for(Splay* y; x != root; ){ y = x->f; if(y != root) (x->d() ^ y->d()) ? rotate(x): rotate(y); rotate(x); }}void insert(Splay *q){ Splay *p = root; for(;;){ int d = q->a > p->a; if(p->c[d] != null) p = p->c[d]; else {p->sc(q, d), splay(q); break;} }}int n, ans;void init(){ scanf("%d", &n);}void work(){ int x; Splay *q, *tmp; null->a = inf; scanf("%d", &x); q = new Splay(); q->a = x; q->c[0] = q->c[1] = q->f = null; root = q; ans += x; for(int i = 1; i < n; i++){ scanf("%d", &x); q = new Splay(); q->a = x; q->c[0] = q->c[1] = q->f = null; insert(q); int t1 = inf, t2 = inf; if(q->c[0] != null){ tmp = q->c[0]; while(null != tmp->c[1]) tmp = tmp->c[1]; t1 = tmp->a; } if(q->c[1] != null){ tmp = q->c[1]; while(null != tmp->c[0]) tmp = tmp->c[0]; t2 = tmp->a; } ans += min(abs(x - t1), abs(t2 - x)); }新聞熱點
疑難解答
