题解：P8672 [蓝桥杯 2018 国 C] 交换次数

AFO_Lzx · 2024-10-16 13:44:00 · 题解

题目传送门

\texttt{Descritption}

给定一个字符串，其中只有 \texttt{A} 和 \texttt{B} 还有 \texttt{T} 三种字母，现在要把它变成每个字母都在一起的形式，只能够将字母进行交换，每次只能交换两个字母，问最少的交换次数。

\texttt{Solution}

我们都知道，最后的排列情况只可能有 6 种，它们分别是 \texttt{ABT,ATB,BAT,BTA,TAB,TBA} 这六种排列，于是，我们就可以用 \texttt{DFS} 全排列的方式来枚举这几种情况，然后计算出需要交换的次数来更新答案。

\texttt{Code}

不贴代码。