蓝桥杯基础练习VIP-完美的代价-题解（C++代码）

解题思路:

1.Impossible

maamdmaam--->奇数个字符出现的次数为1或0时才能实现回文

统计 每个字符出现的次数，如果出现奇数的次数>1时，这时表示不能实现回文

a--z

实现回文交换

mammaaaaadm://可以使用循环交换，也可以使用递归交换(case采用递归交换)

2.从最后面查找第1个出现的位置

3.将一个字符交换到指定的位置

dmama--->mdama

4.奇数个字符的处理 

参考代码:

#include<iostream>
#include<cstring>
#include<cstdio> 
using namespace std;
char arr[8005];
int b[30]; 
int N,count;
int main(){
	//输入 
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>arr[i]; 
		b[arr[i]-'a']++;
	}
	//统计字符串中每个字符出现的次数 
	//如果字符串中有字符单数的次数>1,表示不可能交换成回文数 
	for(int i=0,flag=0;i<26;i++){
		if(b[i]%2==1){
			if(++flag>1){
			    cout<<"Impossible"<<endl;
				return 0;
			}
		}
	}
	int start=0,j,flag;
    for(int i=0;i<N/2;i++){
	     flag=0;
    	 for(j=N-i-1;j>i;j--){
    		if(arr[i]==arr[j]){
    				for(int start=j;start<N-i-1;start++){
		               char temp=arr[start];
		               arr[start]=arr[start+1];
		               arr[start+1]=temp;
		               count++;
	                }
	                break;//第一次出现相等的时候 
    		}		
        }
	    if(j==i){
    	  char temp=arr[i];
		  arr[i]=arr[i+1];
		  arr[i+1]=temp;
		  count++;
		  flag=1;
    	}
    	if(flag==1){
    		i--;
    	}
    }
	
    cout<<count<<endl;
}

PS:欢迎小伙伴多多交流！！！

后期会继续完善代码及解题思路~~~