检查是否有可能使用给定的操作

Question

我有以下问题进行排序排列：
我的任务是，以确定是否有可能进行排序给出的置换，但仅使用一种类型的操作：我们可以将第i元素两个位置在左边。同样，元素i-1和i-2向右移动一个位置。

例如： 可以对排列进行排序（2,5,3,4,1），但我们不能用排列（2,3,5,4,1）进行排列。

（2,5,3，4 ，1）
（2,4,5-，，1）
（2,3,4,5-，1 ）
（ 2,3，,4,5）
（1,2,3,4,5）

复杂性应该可能是线性的。 我想出了二次方案，但它太慢了。我尝试了贪婪的方法，但失败了。

这个问题让我完全陷入困境。

Answer 1

如果存在偶数个反转，则可以仅使用此操作对排列进行排序。您可以使用O（n log n）中的合并排序来对反演进行计数。