不理解为啥题解说每次交换逆序对都增加 -2, 0 或 2
查看原帖
不理解为啥题解说每次交换逆序对都增加 -2, 0 或 2
353688
王熙文楼主2023/1/1 20:45

如果单独考虑三个数是这样的,但是如果三个数中间掺了别的数,也要考虑这些数的贡献啊。比如 1,3,2,41,3,2,4,轮换的三元组是 1,2,41,2,4 三个数,那么轮换完了就是 4,3,1,24,3,1,2,轮换前是 11 个逆序对,轮换后是 55 个逆序对,不满足题解说的。

所以我猜每次轮换后逆序对改变偶数个,但是不会证明,求解。其次即使这样还需要构造方案,题解也没说。

2023/1/1 20:45
加载中...