arrays - 算法 - 以最少的交换两个连续元素的数量对数组进行排序

Question

我要解决的问题已在 2007 年的 USACO 竞赛中给出。简而言之，您将获得一个整数数组，并且可以交换连续的元素 (A[i], A[i+1 ]).在最少数量的交换操作之后，数组必须按升序排序或者是其排序版本的两个连续部分的串联。一个例子:

1, 2, 3, 4
3, 4, 1, 2
4, 1, 2, 3

问题需要在O(N)或O(log(N))时间内解决；再多的话就太慢了。没有针对此特定问题的评论或源代码。我已经提到了索引树和倒置，但我无法理解相关性，因为我只被允许对连续的项目执行交换操作。问题说明可见here .

Answer 1

一个排列相对于另一个排列的反转次数是将一个排列转换为另一个排列所需的最少相邻交换次数。一点点抽象代数表明我们有兴趣找到输入数组的旋转，它可以最小化相对于排序顺序的反转次数。

有几种计算倒置的算法。此处有用的是使用二进制索引树使以下伪代码快速运行 (O(n log n))。

Let P[1], ..., P[n] be the input permutation on 1, ..., n
For k = 1, ..., n
    Initialize A[k] = 0
End For
For j = 1, ..., n
    I[P[j]] = A[j]    # Number of elements before and greater than P[j]
    For k = 1, ..., P[j] - 1    # Replace this loop with an O(log n) tree operation
        A[k] = A[k] + 1
    End For
End For
The total number of inversions is I[1] + ... + I[n]

现在，如果我们将一个元素 j 从数组末尾旋转到开头，我们将更新

For k = 1, ..., j - 1    # Replace this loop with an O(log n) tree operation
    I[k] = I[k] + 1
End For
I[j] = 0

并相应地在恒定时间内重新计算总和。重复适当的次数并取最少的次数。