資訊圈一直以來流傳著一道怪題目,題序如下:
給你n條線段,每條線段給你以x座標左端點與右端點來表示。請問哪一個x座標上面有最多條線段通過,以及這個通過的數量是多少?
身為建電最強學術的阿蘇,當然也花費了很多時間在這題上面。
有一天,阿蘇突然想到,如果把端點做了一些排序之類的操作,他就可以將此問題的複雜度從$O(n^2)$壓到$O(n)$。他將此做法發表在國際知名期刊上,獲得的全世界資訊競賽圈的肯定。
這就是鼎鼎大名的線段蘇優化的由來。
成功獲得國際聲望的阿蘇自己便自己跑去ACM領獎了,留下AaW一個人在空無一人的社辦裡面,孤獨的亂掰著小社賽的題序。
望著空空如也的社辦,AaW坐在沙發上發愣著。
千里孤墳,無處話淒涼
塵滿面,鬢如霜。
想到自己還是進不了間中校隊,AaW不禁流下了一滴滴眼淚。
最近AaW的心情真的很不穩定,常常陷入如雲霄飛車般的起伏當中,具體一點的話,他的心情起伏大概跟底下這張圖一樣,呈現直角形的曲線:
眼淚順著AaW的臉龐留下,滑入了他的嘴角中,一股鹹味湧上舌尖,AaW心頭一震......
這...這是..Brine!!!
全拆國低中的偶像突然地出現在AaW的面前,令AaW大感震驚。
「你...為什麼會出現?」\\
Brine不回答,靜靜的流向剛剛的AaW畫的那張圖中。
只見那張圖的下半部慢慢的被鹽水淹沒,留下了一座座島嶼。
「這...這是......完美的資訊問題!!!」AaW立馬看出這是一題成功解出後就可以超越阿蘇成就的絕佳問題。
於是,AaW想請問你,如果Brine可以自由決定他要淹水的高度,那麼最多AaW的心情圖中可以留下幾座島嶼?
喔對了,如果有一處的地形高度和水位高度一致,則此處仍視為被水面淹過。
第一行給個正整數n,代表此圖表橫向總共可以被切成n塊寬度一致的矩形。
第二行有$n$個正整數,給一個高度$h_i$,代表第i塊矩形的高度。
$1 \le n \le 10^6, 1 \le h_i \le 10^9$
請輸出一個正整數,代表在可以任意調整水位高度時,最多可以留下幾座島嶼?
順帶一提的是,因為$h_i \ge 1$,所以當水位高度為0時,全部算是1座島嶼。
以上圖這樣為例,是3個島嶼
以上圖這樣為例,是4個島嶼
可以發覺的是,這條曲線最多就只能產生4個島嶼
話說,這題和線段蘇有關聯喔...
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~13 | $1 \le n \le 100, 1 \le h_i \le 100$ | 50 |
2 | 0~23 | $1 \le n \le 1000000 , 1 \le h_i \le 1000000000 \, $ | 50 |