题解

思路

定义势能 $F(P)=\sum_i|P_i-i|$。

做法

一次合法交换位置 $i<j$ 时，中间位置都已归位，因此两端元素要么都在区间同侧，要么分别越过自己的目标；计算可知势能的下降量至多为 $2(j-i)$，故任意方案总代价至少为 $F(P)/2$。

若排列尚未有序，把未归位位置从小到大列出：最左端元素必偏右，最右端元素必偏左，所以存在相邻的未归位位置分别偏右、偏左，交换它们合法且恰让势能下降两倍操作代价。

复杂度

反复如此可达到下界，答案就是 $\frac12\sum_i|P_i-i|$，时间复杂度为 $O(N)$，额外空间为 $O(1)$。