请求撤下除第一篇题解外所有题解
查看原帖
请求撤下除第一篇题解外所有题解
590600
Kreado楼主2024/3/7 21:36

rt,理由如下

  1. 由于之前的题解审核很烂(或者没有审核),导致该题题解大部分都很烂,这点母庸质疑。

  2. 该题第一步就是将模型转换,a,ba,b 序列中排名相等的数在同一个位置是最优的,这个贪心需要用排序不等式证明,而不是一眼得出的。

  3. 本题离散化是将序列 aa 排序得到 a′a',那么离散化数组 AiA_i 为 ai′a'_i 在原序列 aa 的位置(这种应该不叫离散化),而非我们常见的离散化,用二分,map 做的那些,而大部分题解都没有解释怎么离散化,这误导了大部分萌新,具体可以看讨论区求助。

  4. 有些题解讲了怎么离散化,如下

序列 aa ,我们假设为 1,7,2,41,7,2,4。

那么离散化后的数组应该是 1,4,2,31,4,2,3。

离散化是正确的,然而代码又给出 3. 的离散化,也就是说代码和题解讲的根本不是一个玩意???

  1. 经过 3. 的离散化后,我们会得到新的 A,BA,B 数组,然后题解又引出了一个新的数组 pp,让 pAi←Bip_{A_i}\gets B_i,然后数组 pp 的逆序对就是答案,这点也是,大部分题解没有解释,解释的是错的,或者上面的思路根本对不上下面的思路。

经过 3. 的离散化后我们很容易得到问题转换成了如何用最少的次数将 AA 数组修改成 BB(这里的修改已经不是交换了)。

我们固定 BB,问题也就转换成了对于每个 ii,在原序列 aa 中排名为 ii 的数在位置 AiA_i,我们要让它来到位置 BiB_i。

此时我们用一个辅助数组 pip_i,pAi←Bip_{A_i}\gets B_i,这样 pp 和数组 AA 构成双射,当 pp 变为有序数组时,对应回 AA,有 A=BA=B,进而一步得到 a=ba=b。

而至于逆序对,这不是本题的重点,这里不多阐述。

综上,我建议撤下除第一篇题解以外的所有题解。

2024/3/7 21:36
加载中...