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

Question

我一直在 spoj 上尝试这个问题，但无法提出正确的方法。解决问题的正确算法是什么？

Answer 1

You should find longest consecutive increasing subsequence, which can be done in O(n log n) (by sorting array), after that, the number of changes needed is N - longest consecutive increasing subsequence. Note that by consecutive I mean there order in sorted array.

e.g:

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.

Why this works:

Best algorithm does not changes some of a items places, call biggest subsequence without changes as X, you wont change the position of X items related to each other during operations, so they should be sorted in increasing mode. But because you just allowed to move some items in the first or the last of array, you can't put any item between X items (note that we assumed X is biggest unchanged subsequence during operations), So there should be no gap between X items. so they should be sorted and consecutive in sorted format.

So number of changes needed couldn't be smaller than the N- length of X, but also is not hard to do your job with N-length of X operation.