解题思路
题目要求通过若干次操作,将初始排列调整为目标排列 [1,2,…,n],且每次操作后所有工位上的工件数量仍是一个排列。一次操作定义为选择两个不同工位 i,j,令 ai 增加 1,aj 减少 1。我们需要求出操作次数最少的方案并输出任意一组最优操作序列。
关键性质:
可以证明,若某次操作中 ai 从 v 变为 v+1,aj 从 v+1 变为 v,则操作前后工件数量的多重集保持不变,仍构成排列。其他情况均无法同时满足“操作后仍是排列”的条件。因此,每一次合法的操作等价于交换两个相邻数值 v 和 v+1 所在的工位。
设 pos[v] 表示当前数值 v 所在工位的编号。目标为 pos[1]<pos[2]<⋯<pos[n]。初始状态下,若存在 v 使得 pos[v]>pos[v+1],则 (v,v+1) 构成一对逆序。交换 v 与 v+1 的位置恰好能消除这一对逆序,且不引入其他逆序。