自动搬运

查看原文

来自洛谷，原作者为

	wuhan1234 **

搬运于2025-08-24 22:41:19，当前版本为作者最后更新于2023-03-31 08:57:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1. 编程思路。

题目中的字母有 B、T、A 这 $3$ 种，$3$ 种字母有 $6$ 种排列方式（BAT、BTA、ABT、ATB、TAB、TBA），对每种排列方式求出其最少的交换次数，取 $6$ 个最少交换次数的最小值就是所求的答案。 下面我们来讨论将只包含 $A$、$B$、$C$ 三种字母的字符串 $S$ 按 $ABC$ 进行排列需要的最少交换次数。

先统计出字符串 $S$ 中 $A$、$B$、$C$ 三种字母各自的个数，不妨分别记为 $acnt$、$bcnt$、$ccnt$。字符串 $S$ 按要求排列好后，应该分成 $A$、$B$、$C$ 三段（或三个区域），其中第 $1$ 段应该是 $acnt$ 个 $A$，第 $2$ 段应该是 $bcnt$ 个 $B$，第 $3$ 段应该是 $ccnt$ 个 $C$。

我们先考察第 $1$ 段，这一段应该全部放字母 $A$。第 $1$ 段不是字母 $A$ 的字符肯定要换到后面的两段中去，其个数记为 $f1t23$（表示需要从第 $1$ 段换到后面的第 $2$、$3$ 两段的非 $A$ 字母个数）。但是这个不是 $A$ 的字符究竟换到后面的哪一段还是有讲究的，如果是字母 $B$，显然换到第 $2$ 段更好些，为此也统计出第 $1$ 段中优先换到第 $2$ 段的字母 $B$ 的个数，记为 $f1t2$。

再考察第 $2$ 段，这一段应该放 $bcnt$ 个字母 $B$。不是字母 $B$ 的字符 $A$ 肯定要换到第 $1$ 段，其个数记为 $f2t1$，字符 $C$ 肯定要换到第 $3$ 段，其个数记为 $f2t3$。

前 $2$ 段全部排好了，剩下的第 $3$ 段肯定会排好，就不再考察了。

在前面的考察中，若 $f1t2= f2t1$，也就是说第 $1$ 段正好有 $x$ 个 $B$ 需要换到第 $2$ 段，而第 $2$ 段中正好有 $x$ 个 $A$ 需要换到第 $1$ 段，则它们直接交换肯定皆大欢喜，交换次数也最少。这种情况下，需要的最少交换次数为 $f1t23+f2t3$。注意：$f1t23$ 次数中包括 $f1t2$ 次数的。

若 $f1t2<f2t1$，此时第 $2$ 段有 $f2t1$ 个 $A$ 需要换到第 $1$ 段，但第 $1$ 段可以换过来的 $B$ 只有 $f1t2$ 个，不够，但第 $2$ 段的 $A$ 是必须换到第 $1$ 段的，因此，只能先将第 $1$ 段的 $f2t1-f1t2$ 个 $C$ 先换到第 $2$ 段，最后再将这 $f2t1-f1t2$ 个 $C$ 交换到第 $3$ 段。因此，需要的最少交换次数为 $f1t23+f2t3+f2t1-f1t2$。

若 $f1t2>f2t1$，此时第 $2$ 段只有 $f2t1$ 个 $A$ 需要换到第 $1$ 段，但第 $1$ 段可以换过来的 $B$ 却有 $f1t2$ 个，多了。将这些多余的 $B$ 先换到第 $3$ 段中，到时会在第 $2$ 段的 $C$ 必须交换到第 $3$ 段时与它们交换，换回到第 $2$ 段，不会多增加交换次数。因此，需要的最少交换次数为 $f1t23+f2t3$。

所以，当 $f1t2<f2t1$ 时，最少交换次数为 $f1t23+f2t3+f2t1-f1t2$。这点也可以这样理解。在第 $1$ 段的 $f1t23$ 个非 $A$ 字母交换完成后，第 $2$ 段字母 $C$ 的个数就是交换前第 $2$ 段 $C$ 的个数（$f2t3$）加上从第 $1$ 段换过来的 $C$ 的个数（$f2t1-f1t2$）。

当 $f1t2\ge f2t1$ 时，最少交换次数为 $f1t23+f2t3$。

2. 源程序。

#include <stdio.h>
#include <string.h>
int calc(char s[],char a,char b,char c) // 将字符串s 按 ABC 顺序排列需要的最少交换次数
{
    int acnt=0,bcnt=0,ccnt=0;
    int f1t23=0,f1t2=0,f2t1=0,f2t3=0;
    int i;
    for (i=0;i<strlen(s);i++)       // 统计字符串 s 中 A、B、C三种字符各自的个数
    {
        if (s[i]==a) acnt++;
        else if (s[i]==b) bcnt++;
        else ccnt++;
    }
    for (i=0;i<acnt;i++)          // 先看第1段,应该放acnt个字符A
    {
        if (s[i]!=a) f1t23++;      // 第1段不是A的字符要换到后面2、3两段中
        if (s[i]==b) f1t2++;       // 第1段是B的字符，优先换到第2段中
    }
    for (i=acnt;i<acnt+bcnt;i++)  // 再第2段的情况，应该放bcnt个字符B
    {
        if (s[i]==a) f2t1++;      // 第2段中的A 肯定换到第1段中
        if (s[i]==c) f2t3++;      // 肯定要换到第3段去
    }
    int  res = f1t23 + f2t3 ;
    if (f2t1>f1t2) res+=(f2t1 -f1t2);
    return res;
}
int main()
{
    char s[100005];
    scanf("%s",s);
    char c[][4]={"BAT","BTA","ABT","ATB","TAB","TBA"};
    int ans=0x7f7f7f7f;
    int i;
    for (i=0;i<6;i++)
    {
        int t=calc(s,c[i][0],c[i][1],c[i][2]);
        if (t<ans) ans=t;
    }
    printf("%d\n",ans);
    return 0;
}