NOIP 普及组初赛 · NOIP 2008 普及组初赛试题 第 14 题

将数组 $\{8, 23, 4, 16, 77, -5, 53, 100\}$ 中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次。

这题考的是置换环分解。拿到题先别急着排，把目标序列画出来，看每个数当前在哪、该去哪，连线找环，环数减一就是最少交换次数。

最容易错在把交换次数想成 n-1，或者数错环的数量。比如把两个环当成一个，或者漏掉长度为1的不动点环。记住：每个环内部只需k-1次交换，环与环之间互不干扰，总次数就是所有环的(k-1)之和，也就是n减去环的个数。

考点与概念

这道题考查的是置换环分解在排序中的应用。核心结论很简单：要把一个排列变成目标顺序，最少交换次数 = 元素总数 n − 环的个数。

命题视角：为什么考这个？

命题人爱在“看似要全排”的题目里挖一个数学模型。它不考具体算法实现，只考你对“交换操作本质”的理解：每次交换最多把一个环拆成两个，或者把两个环合并成一个。所以最优策略就是每个环内部用 k−1 次交换搞定，环与环之间互不干扰。