蓝桥杯2018年第九届真题-交换次数-题解（C++代码）

解题思路:先引用一下　　作者: 优雅的伊利　的解题思路：

因为只有只有3个字母（B,T,A），可以考虑暴力，分成三个区域A B C。
3个字母有6种排列方式。对于任意一种方式进行求解，然后取出最小值即可。
例如求解的顺序是BAT，我们要先得出要放B的位置上有多少个非B的数，然后这些位置肯定是和后面的AT交换的，但是和谁交换也是有要求的，A肯定要先和在A区间上的B交换，实在没有再放到T的区间上，然后再是A和T交换。总的来说，在B区间非B的数量与B区间交换完成后在A区间非A的数量和。

问题的关键在于想清楚 res = Abc + Bc + Ba - min(Ba,Ab)这个部分是怎么来的。将字符串分成三个部分ABC，计算ABC各部分的长度。下面重点来了！！！

A的非a部分是一定会交换到B和C上的（即Abc）。

在A区的b(Aa)和B区的a(Ba)交换时，A区的b的个数不一定够(Ab<Ba)，怎么办？只能将A 区的c交换到B区，而这一部分最后还要再换回到C区的（Ba-Ab)。

A区的b(Aa)和B区的a(Ba)交换时，A区的b的个数够用甚至有余(Ab>=Ba),A区的b除了交换到B区，还会交换到C区，但这一部分b会再与B区的c交换时会回到B区，所以交换的次数是0（Ba-Ba）。

在A区非a交换完成后，B区c的个数就是交换前B区c的个数（Bc）和交换后多的c的个数Ba-min(Ab,Ba)。

所以最后每次循环交换的次数res = Abc + Bc + Ba - min(Ba,Ab)。

注意事项:

INF = 0x3f3f3f3f，一定要取得足够大。

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
string s;
const int INF = 0x3f3f3f3f;
int func(string s,char A,char B,char C){
 int a=0,b=0,c=0;
 int Abc=0,Ab=0,Ba=0,Bc=0,res;
 int i,j;
 for(i=0;i<s.size();i++){
  if(s[i]==A)a++;
  if(s[i]==B)b++;
  if(s[i]==C)c++;
 }
 for(i=0;i<a;i++){
  if(s[i]!=A)Abc++;
  if(s[i]==B)Ab++;
 }
 for(i=a;i<a+b;i++){
  if(s[i]==A)Ba++;
  if(s[i]==C)Bc++;
 }
 res = Abc + Bc + Ba - min(Ba,Ab);
 return res;
}
int main(){
 while(cin>>s){
  int min=INF;
  int res; 
  char c[][4]={"BAT","ATB","TBA","BTA","ABT","TAB"};
  for(int i=0;i<6;i++){
   res=func(s,c[i][0],c[i][1],c[i][2]);
   if(res<min)min=res;
  }
  cout<<min<<endl;
 }
 return 0;
}