PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Prob_Solve
[問題] 演算法問題
作者:
cutekid
(可愛小孩子)
2014-08-01 16:48:20
N 個整數(不重複)
N1,N2,N3,N4...Nn
針對每個 Ni
求 Ni+1,Ni+2,Ni+3...Nn 當中小於 Ni 的值有幾個
例:
Input : 4,3,1,5,2
Output: 3,2,0,1,0
請問這個有比 O(n^2) 更好的算法嗎
謝謝 :)
作者:
yr
(Sooner Born Sooner Bred)
2014-08-01 16:59:00
不是排個序就好了? O(n log n)理解錯問題,請無視 XD
作者: yvb
2014-08-01 17:22:00
樓上的理解其實也沒錯, 稍微轉化一下, 即可適用此題 :)
作者:
cutekid
(可愛小孩子)
2014-08-01 17:27:00
可以請 yvb 大開示一下嗎 :)
作者:
flere
(人間失格)
2014-08-01 18:48:00
用線段樹可以做到O(n log n)..感覺有別的方法OAO
作者:
dreamoon
(千古悲情人物)
2014-08-01 18:56:00
" target="_blank" rel="nofollow">
這是相關文章,搜尋 逆序數對+樹狀數組應該可以搜到很多東西
作者:
lNishan
(紫小霓)
2014-08-01 19:04:00
推月神 <(_ _)>
作者:
FRAXIS
(喔喔)
2014-08-01 19:54:00
如果是單純算inversion 用線段樹會比較快嘛?
作者:
johnathan717
(柏良)
2014-08-01 22:49:00
如果mergesort排序可以一邊排,一邊數inversions
作者:
FRAXIS
(喔喔)
2014-08-02 07:49:00
我也是這樣覺得 使用線段數有什麼好處嘛?
作者: fenzhang (分帳)
2014-08-03 00:18:00
線段樹可以處理動態情況,例如每次修改某個數字
作者:
FRAXIS
(喔喔)
2014-08-03 20:37:00
那當問題是靜態的時候 線段樹應該就沒有優勢了吧?
作者:
DJWS
(...)
2014-08-03 20:52:00
時間複雜度都一樣 有沒有優勢就看實作功力囉
作者:
suhorng
( )
2014-08-04 13:38:00
可能沒有. 當然比賽時線段樹可能有模板, 可以直接套.但他常數也可能比較大啦 只不過是 trade-off
作者: trail0721 (大肚魚)
2014-08-20 13:29:00
Ni+1,Ni+2,Ni+3...Nn=>有序遞增, i.e; 3,4,5,6,7,8,9..輸入 8 => 輸出 (8-3) = 5哈~~~~ 輕鬆一下...
作者:
DJWS
(...)
2014-10-03 09:50:00
归并树 / 划分树
繼續閱讀
Re: [問題] 決定性(判定)問題的三種說法
suhorng
[問題] 決定性(判定)問題的三種說法
dharma
[請益] SPOJ Challenge Problem
bleed1979
Fw: [問題] 編碼or密碼學,達到資料回復
ccoococo
Re: [問題] 請問向量夾角除了利用tan-1之外還有其他方法嗎?
iamstudent
Re: [問題] 請問向量夾角除了利用tan-1之外還有其他方法嗎?
neutrino
Re: [問題] 請問向量夾角除了利用tan-1之外還有其他方法嗎?
euph
Re: [問題] 請問向量夾角除了利用tan-1之外還有其他方法嗎?
DJWS
[問題] 請問向量夾角除了利用tan-1之外還有其他方法嗎?
euph
Re: [請益] Pow function source file
EdisonX
Links
booklink
Contact Us: admin [ a t ] ucptt.com