[理工] 演算法問題 QQ153 PTT批踢踢實業坊

作者: QQ153 (小楊) 2021-11-08 07:14:32

想請問一下這一題
https://imgur.com/8ruyb7f
我覺得跟這題很像想嘗試做看看
但目前沒甚麼想法
在請各位大神指點了
https://imgur.com/bINUZSN
https://imgur.com/lDbeYNCd

作者: VF84 (Jolly Roger) 2021-11-08 07:48:00

用講的太麻煩，我直接PO圖https://imgur.com/a/MDRsVOp因為你的第二張圖連結掛了，所以我沒有完全參考你給的做法簡單來說，就是用 merge sort 的技巧去算阿對了，我遞迴沒有給終止條件，不過，隨便啦，重點不在哪裡

作者: QQ153 (小楊) 2021-11-08 10:39:00

這樣如果條件給ai>aj的話就是把*2給拿掉而已嗎在此重新附上連結http://imgur.com/lbeYNCd

作者: VF84 (Jolly Roger) 2021-11-08 12:00:00

ai>aj 的話，把*2拿掉就可以了沒錯

作者: QQ153 (小楊) 2021-11-08 15:28:00

感謝瞭解了

作者: alan23273850 2021-11-09 08:55:00

逆序數對的經典解法就是 merge sort 和 binaryindexed tree 兩種而已

作者: VF84 (Jolly Roger) 2021-11-09 11:13:00

binary indexed tree...好懷念的名字研究所考試應該不至於出現那種東西www

作者: mathtsai (mathtsai) 2021-11-13 01:15:00

逆序數對觀念就是用Divide&Conquer寫起來和merge sort很像只是改點東西在merge的時候順便去計算給定的條件即可

繼續閱讀