题解：AT_arc218_c [ARC218C] Amidakuji

· · 题解

诈骗题。首先必须注意到 n\ge 3 时，m_{\min} 恰为 2。

接下来考虑 $m=2$ 时的构造。显然任意排列均可通过一个排列交换相邻元素（冒泡）得到，于是我们据此想出一种构造，分别是一个循环移位、一个前两个元素互换其他不变，即 $2,3,\dots,n,1$ 和 $2,1,3,\dots,n$。考虑次数限制 $2n^2$，$O(n^2)$ 的相邻交换很难不让我们想到冒泡排序，我们钦定目标排列为新的序关系对初始排列模拟冒泡排序即可。众所周知冒泡排序最坏次数 $\frac {n(n-1)}2$，相邻冒泡间需循环移位一次，共需约 $n(n-1)$ 次，所以不同轮间 $n$ 次循环移位是可以接受的，于是本题就做完了。