rt,理由如下
-
由于之前的题解审核很烂(或者没有审核),导致该题题解大部分都很烂,这点母庸质疑。
-
该题第一步就是将模型转换,a,b 序列中排名相等的数在同一个位置是最优的,这个贪心需要用排序不等式证明,而不是一眼得出的。
-
本题离散化是将序列 a 排序得到 a′,那么离散化数组 Ai 为 ai′ 在原序列 a 的位置(这种应该不叫离散化),而非我们常见的离散化,用二分,map 做的那些,而大部分题解都没有解释怎么离散化,这误导了大部分萌新,具体可以看讨论区求助。
-
有些题解讲了怎么离散化,如下
序列 a ,我们假设为 1,7,2,4。
那么离散化后的数组应该是 1,4,2,3。
离散化是正确的,然而代码又给出 3. 的离散化,也就是说代码和题解讲的根本不是一个玩意???
- 经过 3. 的离散化后,我们会得到新的 A,B 数组,然后题解又引出了一个新的数组 p,让 pAi←Bi,然后数组 p 的逆序对就是答案,这点也是,大部分题解没有解释,解释的是错的,或者上面的思路根本对不上下面的思路。
经过 3. 的离散化后我们很容易得到问题转换成了如何用最少的次数将 A 数组修改成 B(这里的修改已经不是交换了)。
我们固定 B,问题也就转换成了对于每个 i,在原序列 a 中排名为 i 的数在位置 Ai,我们要让它来到位置 Bi。
此时我们用一个辅助数组 pi,pAi←Bi,这样 p 和数组 A 构成双射,当 p 变为有序数组时,对应回 A,有 A=B,进而一步得到 a=b。
而至于逆序对,这不是本题的重点,这里不多阐述。
综上,我建议撤下除第一篇题解以外的所有题解。