作者QQ153 (小楊)
看板Grad-ProbAsk
標題[理工] 演算法問題
時間Mon Nov 8 07:14:32 2021
想請問一下這一題
https://imgur.com/8ruyb7f
我覺得跟這題很像想嘗試做看看
但目前沒甚麼想法
在請各位大神指點了
https://imgur.com/bINUZSN
https://imgur.com/lDbeYNCd
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.88.219 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1636326874.A.711.html
1F：推 VF84: 用講的太麻煩，我直接PO圖 11/08 07:48
3F：→ VF84: 因為你的第二張圖連結掛了，所以我沒有完全參考你給的做法 11/08 07:49
4F：→ VF84: 簡單來說，就是用 merge sort 的技巧去算 11/08 07:50
5F：推 VF84: 阿對了，我遞迴沒有給終止條件，不過，隨便啦，重點不在哪裡 11/08 07:53
6F：→ QQ153: 這樣如果條件給ai>aj的話就是把*2給拿掉而已嗎 11/08 10:39
7F：→ QQ153: 在此重新附上連結 11/08 10:40
9F：推 VF84: ai>aj 的話，把*2拿掉就可以了沒錯 11/08 12:00
10F：→ QQ153: 感謝 瞭解了 11/08 15:28
11F：推 alan23273850: 逆序數對的經典解法就是 merge sort 和 binary 11/09 08:55
12F：→ alan23273850: indexed tree 兩種而已 11/09 08:55
13F：推 VF84: binary indexed tree...好懷念的名字 11/09 11:13
14F：→ VF84: 研究所考試應該不至於出現那種東西www 11/09 11:13
15F：推 mathtsai: 逆序數對 觀念就是用Divide&Conquer 11/13 01:15
16F：→ mathtsai: 寫起來和merge sort很像 只是改點東西 11/13 01:16
17F：→ mathtsai: 在merge的時候順便去計算給定的條件即可 11/13 01:27