P9338 [JOIST 2023] 合唱 / Chorus

在舞台上，有 $2N$ 只海狸排成一列。它们是合唱团的成员。每只海狸唱着高音部或低音部。这些信息由一个字符串 $S$ 给出。具体地，如果 $S$ 的第 $i$ 个字符是 $A$，编号为 $i$ 的海狸（从右边看台来看）唱高音。如果 $S$ 的第 $i$ 个字符是 $B$，编号为 $i$ 的海狸唱低音。有 $N$ 只海狸唱高音，有 $N$ 只海狸唱低音。 从现在起，这些海狸将要演唱 $K$ 首歌。然而，因为所有歌曲非常复杂，每只海狸只唱一首歌曲，不会唱其他歌曲。此外，为了使歌声更加美妙，每首歌曲必须满足以下条件： + 至少有一只海狸唱这首歌。 + 唱这首歌的唱高音和唱低音的海狸数量应当相等。 + 如果只考虑唱这首歌的海狸，所有唱高音的海狸都在唱低音的海狸的右边。 指挥家 Bitaro 想找到一种方案，给出哪些海狸唱哪首歌，满足以上所有条件。由于 Bitaro 特别聪明，他注意到这可能无法实现。为了应对这个问题，Bitaro 将交换相邻两只海狸的位置多次，以便有一种方式可以调配海狸，从而满足上述条件。 由于 Bitaro 认为效率很重要，所以他想最小化要执行的操作数。然而，这是一个非常困难的问题。由于您是一位出色的程序员，Bitaro 请求您解决此问题。 编写一份程序，在给出合唱与演唱歌曲数量 $K$ 的信息时，计算 Bitaro 需要执行的最小操作数。请注意，在本任务的限制下，可以执行操作多次，以便有一种方式可以在海狸之间分配歌曲，满足上述条件。

从标准输入读取以下数据: > $N\ K$ > > $S$

向标准输出写入一行。输出应该包含 Bitaro 需要执行的最小操作数。

**【样例解释 #1】** 在该样例输入中，例如 Bitaro 可以进行如下操作。下划线表示被交换的两个海狸的位置。 1. 交换从舞台右侧数第 3 个和第 4 个海狸。 操作后，表示海狸部件分布的字符串变为 $\text{`\texttt{AA\underline{AB}BABBAB}'}$。 2. 交换从舞台右侧数第 8 个和第 9 个海狸。 操作后，字符串变为 $\text{`\texttt{AAABBAB\underline{AB}B}'}$。 操作完成后，Bitaro 可以按如下方式分配歌曲： - 从舞台右侧数第 1, 2, 3, 4, 5, 7 个海狸演唱第一首歌 - 从舞台右侧数第 6, 8, 9, 10 个海狸演唱第二首歌 这种分配方式满足条件。若操作次数少于 2 次，则不存在满足条件的分配方式。因此输出 2。 该样例满足所有子任务的限制。 **【样例解释 #2】** 不进行任何操作时，Bitaro 可以按如下方式分配歌曲： - 从舞台右侧数第 1, 2, 3, 5 个海狸演唱第一首歌 - 从舞台右侧数第 4, 6, 7, 8 个海狸演唱第二首歌 - 从舞台右侧数第 9, 10 个海狸演唱第三首歌 这种分配方式满足条件。因此输出 0。 该样例满足所有子任务的限制。 **【样例解释 #3】** 该样例满足所有子任务的限制。 **【样例解释 #4】** 该样例满足所有子任务的限制。 **【数据范围】** 对于所有测试数据，满足 $1 \le N \le 10^6$，$1 \le K \le N$，$S$ 是长度为 $2N$ 的字符串，且其中字符 $\verb!A!$ 和 $\verb!B!$ 各出现 $N$ 次。保证 $N,K$ 均为整数。 | 子任务编号 | 分值 | 限制 | | :----------: | :----------: | :----------: | | $1$ | $16$ | $N \le 10$ | | $2$ | $24$ | $N \le 500$ | | $3$ | $21$ | $N \le 5000$ | | $4$ | $26$ | $N \le 10^5$ | | $5$ | $13$ | 无 | 提示说明部分，翻译由 DeepSeek R1 完成