CSP-S 提高级 · CSP 2021 提高级第一轮 第 10 题

定义一种字符串操作为交换相邻两个字符。将 $\texttt{DACFEB}$ 变为 $\texttt{ABCDEF}$ 最少需要 ( ) 次上述操作。

这题本质是求逆序对。把目标顺序ABCDEF看作123456，原串DACFEB映射为4,1,3,6,5,2，直接数有多少对(i<j)满足a[i]>a[j]，总数就是最少交换次数。

学生最容易犯的错误是把题目当成任意位置交换，直接套用n-循环节数公式，或者在冒泡模拟时漏数交换次数。还有一个典型坑是把字母本身的大小比较当成依据，比如认为D和F比大小，而不是看它们在目标序列中的相对位置。

考点与概念

这道题考的是排序基础中的逆序对概念。核心定理是：将一个排列通过相邻交换变为升序排列所需的最小交换次数，恰好等于该排列的逆序对数。

什么是逆序对？在序列中，如果位置i < j，但数值a[i] > a[j]，那么(a[i], a[j])就构成一个逆序对。直观理解，逆序对就是“该排在前面的元素跑到了后面”的违规配对。相邻交换一次，最多只能消除一个逆序对（交换相邻的逆序元素），所以逆序对总数就是理论下限。

命题视角

命题人喜欢考这种“模型转化”：表面是字符串操作，底层是排列性质。他们常挖的坑有两个：一是混淆“相邻交换”和“任意位置交换”（后者最小次数=n-循环节数）；二是不会把字符映射成数字序列，直接拿字母表顺序乱比大小。