作者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/cn.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