蓝桥杯 试题 基础练习 完美的代价（详细c++）

题意：每次能执行相邻的字符交换，求让其字符串成为一个回文串要用到的最少的交换次数

思路：如何一个字符串中存在俩个以上的奇数字符的话，那么肯定是构不成回文串的，因为遇到奇数字符我们的处理方法是将其放在中间位置；

那么在其余的情况下，均为可以构成回文串的字符串，我们要想找到最少的操作次数，无非是不要重复的交换。

那么我们从字符串的开头位置开始，到(l+1)/2,这个位置，这是回文串的一半！然后我们要给其配对找另一半。

那么我们要从字符串的末位，开始搜寻到 i （即为对半个字符串遍历的当前位置），因为我们这样子做的话，就是外部排序是好的，就是字符串两边一直是好的，是回文的，然后就这样子一直往内，然后每交换一次，计数加一就行了

AC详细见代码

#include<bits/stdc++.h>

using namespace std;

map<char,int> st;
int tot=0;

int main(){
	int l;
	cin>>l;
	string s;
	cin>>s;
	for(int i=0;i<l;i++){
		st[s[i]]++;//统计各个字符的个数
	}
	map<char,int>::iterator  it;//auto蓝桥杯官网不能用
	for(it = st.begin();it!=st.end();it++){
		if(it->second % 2 == 1){
			tot++;
		} 
	}
	if(tot>=2){//两个以上的奇数字符就不能组成字符串
		cout<<"Impossible"<<endl;
	}
	else{
		int ans = 0;//计数
		int res = l;//长度
			for(int i=0;i<(l+1)/2;i++){//半个字符串遍历
				int j;
				for(j=res-1;j>i;j--){//寻找另一半
					if(s[i] == s[j]){
						while(j<res-1){//放在对的地方
							swap(s[j],s[j+1]);
							j++;
							ans++;
						}
						res--;//找到了下次就缩短查找长度
						break;
					}
				}
				if(i==j)//说明是奇数串！
				 ans += abs((l-1)/2 - i);//不知道单个字符在左还是右，所以用绝对值。
			  }
			  cout<<ans<<endl;
			}
	return 0;
}