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

解题思路:
因为只有只有3个字母（B,T,A），可以考虑暴力。

3个字母有6种排列方式。对于任意一种方式进行求解，然后取出最小值即可。

例如求解的顺序是BAT，我们要先得出要放B的位置上有多少个非B的数，然后这些位置肯定是和后面的AT交换的，但是和谁交换也是有要求的，A肯定要先和在A区间上的B交换，实在没有再放到T的区间上，然后再是A和T交换。总的来说，在B区间非B的数量与B区间交换完成后在A区间非A的数量和。

注意事项:

参考代码:

#include"iostream"

#include"cstdio"

using namespace std;

const int INF = 0x3f3f3f3f;

string s;

char t[][4]={"BAT", "BTA", "ABT", "ATB", "TBA", "TAB"};

int solve(char A, char B, char C){

  int a=0, b=0, c=0;

  for(int i=0;i<s.size();i++) {

    if(s[i] == A) 

a++;

    else if(s[i] == B) 

b++;

    else 

c++;

  }

  int cia=0,cib=0,cic=0,ci=0;

  for(int i=0;i<a;i++){

    if(s[i]!=A)

ci++;

    if(s[i]==B) 

cib++;

  }

  for(int i=a;i<b+a;i++){

    if(s[i]==A) 

cia++;

    if(s[i]==C) 

cic++;

  }

  ci+=cic+cia-min(cib,cia);

  return ci;

}

int main(){

  cin>>s;

  int Min=INF;

  for(int i=0;i<6;i++)

    Min=min(Min,solve(t[i][0],t[i][1],t[i][2]));

  cout<<Min;

  return 0;

}