使陣列排序的最小操作次數

Question

我一直在嘗試this關於spoj的問題，無法拿出正確的方法。 解決問題的正確算法是什麼？

Answer 1

您應該找到最長的連續增加的子序列，可以在O（n log n）中完成（通過排序數組），之後，需要的更改數量爲N - longest consecutive increasing subsequence。請注意，通過連續我的意思是排序數組中的順序。

例如：

1 7 6 2 5 4 3 => 1-2-3最長連續遞增子， 數目的所需移動是4

1 6 4 3 5 2 7 => 1-2或4-5或6-7是最長連續增加 子序列，請注意，1-4-5-7是最長遞增子但 數目的移動需要的是5不3.

爲什麼這個作品：

最佳算法不改變一些的物品的地方，最大的叫無序列變化X，你不會更改的操作過程中相互關聯的X項目的位置，所以他們應該在增長方式進行排序。但是因爲你只是允許移動陣列中的第一個或最後一個物品，所以你不能在X項目之間放置任何物品（注意，我們假設X是操作期間最大的不變的子序列），所以X之間應該沒有差距項目。所以它們應該按排序格式排序和連續。

所以需要的變化次數不能小於N- length of X，但也不難用N-length of X operation做你的工作。