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

解题思路:参考楼上JAVA的

注意事项:

参考代码:

#include <iostream>

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

typedef long long ll;

typedef pair<int,int> P;

#define pi 3.141592653589793238

int mov[4][2]= {{-1,0},{0,1},{1,0},{0,-1}};

int times[30];

string s;

int fun(string order){

    int fir=times[order[0]-'A']-1;

    int sec=fir+times[order[1]-'A'];

    int thir=s.length()-1;

    int res=0;

    int L=fir+1;

    int R=thir;

    string temp=s;

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

        if(temp[i]==order[1]){

            while(temp[L]!=order[0]){

                L++;

            }

            swap(temp[i],temp[L]);

            L++;

            res++;

        }else if(temp[i]==order[2]){

            while(temp[R]!=order[0]){

                R--;

            }

            swap(temp[i],temp[R]);

            R--;

            res++;

        }

    }

    R=thir;

    for(int i=fir+1;i<=sec;i++){

        if(temp[i]==order[2]){

            while(temp[R]!=order[1]){

                R--;

            }

            //swap(temp[i],temp[R]);

            R--;

            res++;

        }

    }

    return res;

}

int main()

{

    freopen("C:/Users/86183/Desktop/input.txt","r",stdin);

    //freopen("‪C:\\Users\\86183\\Desktop\\output.txt","w",stdout);

    ios::sync_with_stdio(false);

    cin.tie(0);

    while(cin>>s){

        int len=s.length();

        memset(times,0,sizeof(times));

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

            times[s[i]-'A']++;

        }

        int res=fun("ABT");

        res=min(res,fun("ATB"));

        res=min(res,fun("BAT"));

        res=min(res,fun("BTA"));

        res=min(res,fun("TAB"));

        res=min(res,fun("TBA"));

        cout<<res<<endl;

    }

    return 0;

}