Description

營業(yè)額統(tǒng)計 Tiger最近被公司升任為營業(yè)部經(jīng)理，他上任后接受公司交給的第一項任務(wù)便是統(tǒng)計并分析公司成立以來的營業(yè)情況。 Tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業(yè)額。分析營業(yè)情況是一項相當(dāng)復(fù)雜的工作。由于節(jié)假日，大減價或者是其他情況的時候，營業(yè)額會出現(xiàn)一定的波動，當(dāng)然一定的波動是能夠接受的，但是在某些時候營業(yè)額突變得很高或是很低，這就證明公司此時的經(jīng)營狀況出現(xiàn)了問題。經(jīng)濟管理學(xué)上定義了一種最小波動值來衡量這種情況： 該天的最小波動值 當(dāng)最小波動值越大時，就說明營業(yè)情況越不穩(wěn)定。 而分析整個公司的從成立到現(xiàn)在營業(yè)情況是否穩(wěn)定，只需要把每一天的最小波動值加起來就可以了。你的任務(wù)就是編寫一個程序幫助Tiger來計算這一個值。 第一天的最小波動值為第一天的營業(yè)額。  輸入輸出要求

Input

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

Output

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

Sample Input

Sample Output

HINT

結(jié)果說明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

該題數(shù)據(jù)bug已修復(fù).----2016.5.15

#include <cstdio>#include <algorithm>using namespace std;const int maxx = 50000 + 100;const int maxn = 1000000 + 100;const int Inf = 1000000000 + 100;int num,n,tot,root,Ans1,Ans2,x;bool done[maxn];struct Node{    int lc,rc;    int v,fix;    int size,cnt;}T[maxx];void update(int i){    T[i].size = T[T[i].lc].size + T[T[i].rc].size + 1;}void lturn(int &i){    int t = T[i].rc;    T[i].rc = T[t].lc;    T[t].lc = i;    T[t].size = T[i].size;    update(i);    i = t;}void rturn(int &i){    int t = T[i].lc;    T[i].lc = T[t].rc;    T[t].rc = i;    T[t].size = T[i].size;    update(i);    i = t;}void insert(int &i,int x){    if(i == 0){        num++;        i = num;        T[i].size = 1;        T[i].v = x;        T[i].fix = rand();        return;    }    T[i].size++;    if(x < T[i].v){        insert(T[i].lc,x);        if(T[T[i].lc].fix < T[i].fix) rturn(i);    }    else{        insert(T[i].rc,x);        if(T[T[i].rc].fix < T[i].fix) lturn(i);    }}void Query_pre(int i,int x){    if(i == 0) return;    if(T[i].v <= x){        Ans1 = T[i].v;        Query_pre(T[i].rc,x);    }    else Query_pre(T[i].lc,x);}void Query_sub(int i,int x){    if(i == 0) return;    if(T[i].v >= x){        Ans2 = T[i].v;        Query_sub(T[i].lc,x);    }    else Query_sub(T[i].rc,x);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&x);        Ans1 = -Inf;		Ans2 = Inf;		Query_pre(root,x);        Query_sub(root,x);        if(i!=1)            tot += min((x-Ans1),(Ans2-x));        else        	tot += x;        insert(root,x);    }    printf("%d/n",tot);    return 0;}