Tiger最近被公司升任為營業部經理，他上任后接受公司交給的第一項任務便是統計并分析公司成立以來的營業情況。 Tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業額。分析營業情況是一項相當復雜的工作。由于節假日，大減價或者是其他情況的時候，營業額會出現一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業額突變得很高或是很低，這就證明公司此時的經營狀況出現了問題。經濟管理學上定義了一種最小波動值來衡量這種情況：
第一行為正整數 ，表示該公司從成立一直到現在的天數，接下來的n行每行有一個整數(有可能有負數) ，表示第i天公司的營業額。
輸出文件僅有一個正整數，即Sigma(每天最小的波動值) 。結果小于2^31 。
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
在splay中查找前驅和后繼即可。
#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)); }新聞熱點
疑難解答
