toj 147 測資是不是有點弱?

domen111

題目敘述說 n<= 100000，理論上O(n^2)應該不會AC，不過剛剛看了別人的AC code好像都是O(n^2) (希望我沒有看錯)。
我寫的一個O(nlgn)的code傳上去雖然AC了，可是卻也沒有比O(n^2)快多少
(覺得我的AC code短短21行好漂亮!)

jd3

我看不懂你的CODE...
為什麼*upper_bound(a,a+i-1,a[i]-a[i-1]); ?

domen111

jd3 發表於 2014-10-4 23:26
我看不懂你的CODE...
為什麼*upper_bound(a,a+i-1,a-a); ?

upper_bound算是二分搜吧，回傳一個iterator指向比(a-a[i-1])大的元素
我的演算法是線性搜尋最長的木棒，如果是可行的(a[i-1]+a[i-2]>a)就二分搜最短的那支木棒(upper_bound)