P8672 [蓝桥杯 2018 国 C] 交换次数 题解
wuhan1234
·
·
题解
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 段。因此，需要的最少交换次数为
若 $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. 源程序。
```c
#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;
}
```