竹園論壇

標題: toj 147 測資是不是有點弱? [打印本頁]

---

作者: domen111    時間: 2014-9-16 21:49
標題: toj 147 測資是不是有點弱?
題目敘述說 n<= 100000，理論上O(n^2)應該不會AC，不過剛剛看了別人的AC code好像都是O(n^2) (希望我沒有看錯)。
我寫的一個O(nlgn)的code傳上去雖然AC了，可是卻也沒有比O(n^2)快多少
(覺得我的AC code短短21行好漂亮!)

---

作者: jd3    時間: 2014-10-4 23:26
我看不懂你的CODE...
為什麼*upper_bound(a,a+i-1,a[i]-a[i-1]); ?

---

作者: domen111    時間: 2014-10-5 12:19

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)

---

歡迎光臨 竹園論壇 (http://forum.tfcis.org/)

Powered by Discuz! X3.2