這果然是在那個(gè)沒(méi)有STL的年代出的題

1588: [HNOI2002]營(yíng)業(yè)額統(tǒng)計(jì)

Time Limit:?5 Sec??Memory Limit:?162 MB
Submit:?16648??Solved:?6683
[Submit][Status][Discuss]

Description

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

Input

第一行為正整數(shù) ，表示該公司從成立一直到現(xiàn)在的天數(shù)，接下來(lái)的n行每行有一個(gè)整數(shù)(有可能有負(fù)數(shù)) ，表示第i 天公司的營(yíng)業(yè)額。 天數(shù)n<=32767, 每天的營(yíng)業(yè)額ai <= 1,000,000。 最后結(jié)果T<=2^31

?

Output

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

Sample Input

6
5
1
2
5
4
6

Sample Output

12

HINT

?

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

對(duì)于這道題只要每處理到一個(gè)數(shù)據(jù)就懟進(jìn)一個(gè)平衡樹(shù)然后查前驅(qū)后繼就可以水過(guò)去w...

$std::set$ 大法好(逃

表示正在籌備OI中的STL教程w(強(qiáng)行刷一波訪問(wèn)量?(逃))

使用STL的參考代碼:

GitHub

1 #include <set> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <iostream> 6 #include <algorithm> 7 8 const int INF=0x7FFFFFFF; 9 10 int main(){ 11 std::multiset<int> s; 12 std::multiset<int>::iterator iter; 13 int n; 14 int tmp; 15 int sum=0; 16 int delta; 17 scanf("%d",&n); 18 scanf("%d",&tmp); 19 s.insert(tmp); 20 sum+=tmp; 21 for(int i=1;i<n;i++){ 22 delta=INF; 23 scanf("%d",&tmp); 24 s.insert(tmp); 25 iter=s.find(tmp); 26 if(iter!=s.begin()){ 27 --iter; 28 delta=std::min(delta,abs(*iter-tmp)); 29 ++iter; 30 } 31 if(++iter!=s.end()){ 32 delta=std::min(delta,abs(*iter-tmp)); 33 --iter; 34 } 35 sum+=delta; 36 } 37 printf("%d\n",sum); 38 return 0; 39 } Backup

日常圖包

?

轉(zhuǎn)載于:https://www.cnblogs.com/rvalue/p/7280415.html

總結(jié)

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

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