a167:
P-3-4. 最接近的高人
內容
對於一個人來說，只要比他高的人就是高人。
有N個人排成一列，對於每一個人，要找出排在他前方離他最近的高人，排在之後的高人不算，假設任兩個相鄰的人的距離都是1，本題要計算每個人和他前方最近高人的距離之總和。
如果這個人前方沒有高人(前方沒人比他高)，距離以他的位置計算(等價於假設最前方有個無窮高的高人)
輸入說明
第一行有一個正整數N，第二行有N個正整數依序代表每個人的身高，相鄰數字間以空白隔開。N≤2e5，身高不超過1e7。
輸出說明
輸出每個人與前方最近高人的距離總和。
範例輸入
#1
8 8 6 3 3 1 5 8 1
範例輸出
#1
18
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (20%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
公開 測資點#0 (20%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
提示 ：
我們可以假設在最前方位置0的地方有個無限大的數字，這樣可以簡化減少邊界的檢查。最天真無邪又直接的方法就是：對每一個i，從i-1開始往前一一尋找，直到碰到比他大的數字或者前方已走投無路。但是這個方法太慢，算一下複雜度，在最壞的情形下，每個人都要看過前方的所有人，所以複雜度是O(n2)。這一題n是2e5，一定是O(n)或O(nlog(n))的方法。
要改善複雜度，要想想是否有沒有用的計算或資料。假設身高資料放在陣列a[]，如果a[i-1] ≤ a[i]，那麼a[i-1]不可能是i之後的人的高人，因為由後往前找的時候會先碰到a[i]，如果a[i]不夠高，a[i-1]也一定不夠高。同樣的道理，當我們計算到i的時候，任何j<i且a[j] ≤ a[i]的a[j]都是沒有用的。如果我們丟掉那些沒有用的，會剩下甚麼呢？一個遞減的序列，只要維護好這個遞減序列，就可以提高計算效率。
標籤:
出處:
AP325
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||