CF1375E题解

陈刀仔 · 2021-11-14 17:04:44 · 题解

冒泡排序有一个与逆序对相关的性质，提出序列中逆序数值对，那么在冒泡排序的过程中，会交换的数值对，正好就是原数组逆序数值对的集合。

这就直接将这个单纯利用逆序对的排序与冒泡排序联系在一起了，但是你固定的是数值，并不能保证交换的始终是那几种逆序下标对。

为了保证下标对相同，我们考虑选择下标。但是如果考虑下标，一次交换后又很可能对其它的逆序下标对产生了影响。

我们需要既考虑逆序下标对，又考虑逆序数值对。

有一个经典套路，构造一个映射数组 b[i] 表示 在位置 i 上 最终应该放置当前位置是 b[i] 的数。

这个数组有一些性质：

• 交换 (a[b[u]],a[b[v]]) ，则 (b_u,b_v) 也会交换。
• 若u<v ，则 a[b[u]]<a[b[v]] 。

不断交换当前的逆序对，一定最终会使得数组有序。

冒泡排序一定会经过所有的逆序对，那么我们对 b 进行冒泡排序，b 有序后，a 也有序了，这样数值对上有了保证。

而且每次交换相邻的 (b[i],b[i+1]) 不会影响到其它的逆序下标对，因为 i 和 i+1 中间没有其它数。

我们只需要记录下来每次需要交换的 (b[i],b[i+1]) ，就是答案。

特判一下相等情况。