思路

• 关键等价：若在某次操作中选择的位置的值分别为 $v$ 与 $v+1$，则操作后它们交换位置；否则不可能保持为排列。 证明要点：多重集计数平衡要求对 $a\to a+1$ 与 $b\to b-1$ 的四个计数改变量相互抵消，只有当 $b=a+1$ 时成立。

• 因而，允许的操作等价于“交换值为相邻数对 $(v, v+1)$ 的两个位置”，这就是在“值空间”的相邻换位。

• 设 $\text{pos}[v]$ 为值 $v$ 的当前位置，则当且仅当 $\text{pos}[v] > \text{pos}[v+1]$ 时，$(v, v+1)$ 构成一对“逆序”。每次交换 $(v, v+1)$ 会恰好使逆序数减少 $1$。

• 令

  $\text{inv}(p)$=$\left|{(i,j)\mid 1\le i<j\le n,\ p_i>p_j}\right|$

题目内容

给定长度为 $n$ 的排列 {$p_1,p_2,…,p_n$}，定义一次操作为：

选择两个不同的位置 $i,j$ ，将 $p_i$ 增加 $1$ ，同时将 $P_j$ 减少 $1$ ;同时需要保证每次操作后，数组仍是 $1$ 到 $n$ 的一个排列。

问将数组变为严格递增排列 {$1,2,…,n$} 需要的最少操作次数。

长度为 $n$ 的排列是由 $1,2,...,n$ 这 $n$ 个整数、按任意顺序组成的数组(每个整数均恰好出现一次)。例如，{$2,3,1,5,4$} 是一个长度为 $5$ 的排列，而 {$1,2,2$} 和 {$1,3,4$} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。