[理工] 算法问题 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的时候顺便去计算给定的条件即可

继续阅读