Description

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

Input

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

Output

輸出文件僅有一個(gè)正整數(shù)，即Sigma(每天最小的波動(dòng)值) 。結(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

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

set模擬平衡樹~

BZOJ上abs不能用cmath的，估計(jì)要加上algorithm……于是就自己寫了一個(gè)~

#include<cstdio>#include<iostream>#include<set>using namespace std;int n,a[100001],x,y,ans;set<int> se;int abs(int u){	return u>0 ? u:-u;}int main(){	scanf("%d",&n);	for(int i=1;i<=n;i++) scanf("%d",&a[i]);	se.insert(a[1]);ans=a[1];	for(int i=2;i<=n;i++)	{		if(se.count(a[i])) continue;		x=*(--se.lower_bound(a[i]));		y=*se.lower_bound(a[i]);		if(!se.count(x)) ans+=abs(y-a[i]);		else if(!se.count(y)) ans+=abs(a[i]-x);		else ans+=min(abs(y-a[i]),abs(a[i]-x));		se.insert(a[i]);	}	PRintf("%d/n",ans);	return 0;}