arrays - 使数组排序的最小操作数

Question

我一直在努力this spoj 上的问题，无法提出正确的方法。解决问题的正确算法是什么？

Answer 1

你应该找到最长的连续递增子序列，这可以在 O(n log n) 中完成(通过排序数组)，之后，需要更改的次数是 N - longest consecutive increasing subsequence .请注意，连续是指排序数组中的顺序。

例如:

1 7 6 2 5 4 3 => 1-2-3 is longest consecutive increasing subsequence, number of moves needed is 4.

1 6 4 3 5 2 7 => 1-2 or 4-5 or 6-7 is longest consecutive increasing subsequence, note that 1-4-5-7 is longest increasing subsequence but number of moves needed is 5 not 3.

为什么会这样:

最佳算法不改变某项的某些位置，将不改变的最大子序列称为X，运行时不会改变相互关联的X项的位置, 所以它们应该以递增的方式排序。但是因为你只允许移动数组第一个或最后一个中的一些项目，你不能在 X 项目之间放置任何项目(注意我们假设 X 是最大的操作期间未更改的子序列)，因此 X 项之间不应有间隙。所以它们应该以排序的格式排序和连续。

因此所需的更改数量不能小于 N-length of X，但使用 N-length of X operation 也不难完成您的工作>.