Description

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

Input

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

Output

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

Sample Input

Sample Output

HINT

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

該題數據bug已修復.----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;}