CSP-S 2021 第一轮 第10题：定义一种字符串操作为交换相邻两个字符。将“DACFEB”变为“ABCDEF"最少

题目

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

选项

• A. 7
• B. 8
• C. 9
• D. 6

答案

A

题解

选 A，7 次。

关键是数“逆序对”：两个字符的先后顺序与字母顺序相反，就算一对。每次交换相邻字符，只能增加或减少 1 个逆序对。

对于 DACFEB：

• D 比后面的 A、C、B 大：3 对；
• C 比后面的 B 大：1 对；
• F 比后面的 E、B 大：2 对；
• E 比后面的 B 大：1 对。

共计： \[ 3+1+2+1=\boxed{7} \]

目标 ABCDEF 的逆序对为 0，因此至少需要 7 次；每次都交换相邻且逆序的字符，就能恰好用 7 次完成。