檢查是否有可能使用給定的操作

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）中的合併排序來對反演進行計數。