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è)額。
天數(shù)n<=32767,
每天的營業(yè)額ai <= 1,000,000。
最后結(jié)果T<=2^31

Output

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

Sample Input

6

5

1

2

5

4

6

Sample Output

12

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

Solution

• 這題是一道裸的平衡樹，練算法的好題。

• 題目是求對于第i個數(shù)，求在前i-1個數(shù)中、最接近這個數(shù)的那個。

• 這其實就相當(dāng)于每次插入操作，求前驅(qū)和后繼。

• 由于這題只有插入和查詢操作，以下代碼使用了簡短的Splay算法。

Code

#include<cstdio> using namespace std; const int N=1<<15+2,MX=1e9; int tot,root,ans; int s[N][2],fa[N],key[N]; inline int read() {int data=0,w=1; char ch=0;while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();if(ch=='-') ch=getchar(),w=-1;while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data*w; } inline int min(int x,int y) {return x<y?x:y; } inline bool pd(int x) {return x==s[fa[x]][1]; } inline void rotate(int x) {int y=fa[x],w=pd(x);if(fa[x]=fa[y]) s[fa[y]][pd(y)]=x;fa[s[y][w]=s[x][w^1]]=y;s[fa[y]=x][w^1]=y; } inline void splay(int x) {for(int y;y=fa[x];rotate(x))if(fa[y]) rotate(pd(x)==pd(y)?y:x);root=x; } inline void ins(int &x,int y,int v) {if(!x){x=++tot;fa[x]=y;key[x]=v;return;}ins(s[x][key[x]<=v],x,v); } inline int search(int x,int v) {while(key[x]!=v)if(key[x]<v){if(!s[x][1]) break;x=s[x][1];}else{if(!s[x][0]) break;x=s[x][0];}return x; } int main() {int n=read(),x=read();ins(root,0,ans=x);ins(root,0,MX);ins(root,0,-MX);while(--n){ins(root,0,x=read());splay(tot);int p=search(s[root][0],MX);int q=search(s[root][1],-MX);ans+=min(x-key[p],key[q]-x);}printf("%d",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1588: [HNOI2002]营业额统计的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。