bzoj1588: [HNOI2002]營業(yè)額統(tǒng)計

2019-11-10 17:24:24

字體：大中小

來源：轉載

供稿：網友

bzoj1588

Description

Tiger最近被公司升任為營業(yè)部經理，他上任后接受公司交給的第一項任務便是統(tǒng)計并分析公司成立以來的營業(yè)情況。 Tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業(yè)額。分析營業(yè)情況是一項相當復雜的工作。由于節(jié)假日，大減價或者是其他情況的時候，營業(yè)額會出現一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業(yè)額突變得很高或是很低，這就證明公司此時的經營狀況出現了問題。經濟管理學上定義了一種最小波動值來衡量這種情況：該天的最小波動值=min{|改天以前某天營業(yè)額?改天營業(yè)額|} $該天的最小波動值 = min/{ | 改天以前某天營業(yè)額 - 改天營業(yè)額 | /}$

Input

第一行為正整數，表示該公司從成立一直到現在的天數，接下來的n行每行有一個整數(有可能有負數) ，表示第i天公司的營業(yè)額。

Output

輸出文件僅有一個正整數，即Sigma(每天最小的波動值) 。結果小于2^31 。

Sample Input

6 5 1 2 5 4 6

Sample Output

Hint

結果說明：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)); }