题解：AT_arc225_d [ARC225D] Gap Swap (easy)

· · 题解

先说结论，答案等于：

\frac{\sum_{i=1}^n |i - p_i|}{2}

下面定义有效交换为对数对 (i,j),i<j 满足 p_i > i,p_j < j，且 \forall k \in (i,j),p_k = k 的交换操作。

下面定义一个数 p_i 的「归宿」为位置 p_i，即这个数最终处于的位置。

如果数列非有序时任意有效交换一定存在，那么不断进行有效交换，每个数 p_i 都会趋近于自己的「归宿」，且总路程恰等于 |i-p_i|。

下面证明有效交换一定存在。

假设不存在有效交换，说明不存在数对 (i,i+1) 满足 p_i > i,p_{i+1}<i+1，即不存在数对满足 p_i > p_{i+1}，说明数列有序，与数列非有序矛盾。

代码不放了。

欢迎找错，欢迎 hack。