給一非負整數序列a1,a2,...,an (n<1000000)
問有多少數對(i,j)滿足
A : 1<=i<j<=n
B : 對所有的i<k<j，滿足ai>=ak且aj>=ak (換句話說，ai和aj必須是[i,j]序列中最大的兩個數)
例如：5 3 1 3 5
滿足的數對有(1,2)(1,4)(1,5)(2,3)(2,4)(2,5)(3,4)(4,5)共八對
程式碼：(傳到zerojudge記得把I64d要換成lld)
1.O(n^3) http://codepad.org/qCLqY9JN
2.O(n^2) http://codepad.org/tGkzt83Z
3.O(n) http://codepad.org/DkuW0rSP
n到百萬級，我們試著把目標訂在設計一個O(n)的算法
先來看看枚舉的狀況如何：
(1)直解，O(n^3)
開兩層for迴圈i,j，並且用一層for迴圈k來檢查ai,aj是不是這中間最大的兩個數
簡單明瞭容易瞭解
(2)把max的部分，利用j本身也會遍歷k的特性優化到O(n^2)
(意即對同一輪i，所有存在的k其實就是曾經檢查過的所有j)
細心的觀察讓算法快上不少，但是對上1000000個數還是不夠快
(3)最終解法O(n)：利用stack
我們來考慮一個情形：2 1 2 99 1 1 1
99(a4)就像一座高山，完全阻隔了a1~a3能和a5~a7溝通的可能性
如果已經通盤考慮a1~a3的溝通對數，遇到a4完全大於前半，
a1~a3就好像被山擋住全部死掉一樣，不可能和5~7形成數對
所以想像一個stack裡面存著的是「目前活著的元素們」(可能當成i來形成數對的元素們)
可以很快的知道，stack裡面的元素永遠會由大排到小，為什麼呢？
試著根據定義放放看這組測資就會明白了
i=1：stk{1}
i=2：stk{1,2}
i=3：stk{1,3}，這時候a3遮住了a2的視線，a2的功能就到此結束了 pop2
i=4：stk{4} 全部被遮住、pop3 pop1
i=5：stk{4,5}
i=6：stk{4,5,6}
i=7：stk{4,5,6,7}
在每次pop的時候，通盤考慮該元素(假設top的編號是x、欲加入的是y)當成i或當成j的可能性
並且記得，在全部跑完以後要把stack清空(跟stack算表達式很像不是嗎)
(插播一下，有n^2的code可以驗證答案真是debug好幫手...)
分成三種情形：
Ⅰ：(x,y)是一對，只有最後清stack的時候不用算這個
Ⅱ：(x-1,x)、(x-2,x)...當x-1,x-2這些值都恰好等於x的時候，共(p-1)組(p=連續ary[x]的數量)
Ⅲ：(x-p,x)，x-p是ary[x]往左走遇到第一個大於ary[x]的元素，只有stack還有元素的時候要算
注意到在Ⅱ這一步要是傻傻的回頭檢察，最壞又會退化變回n^2
所以記錄數組snu[]表示該stack元素的重複數量(stack number)，也就是文中的p值
如此一來因為每個元素至多進和出stack各一次，根據平攤分析得到總時間複雜度O(n)
其他實現的細節都寫在code裡面了，
儘管一開始提交的時候WA了(癥結在第43行忘了sn>0)
我想它表達的邏輯是足夠清楚的
沒有留言:
張貼留言