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

解题思路:

     1.impossible的情况：如果有一个字符出现的次数是奇数次数，而且n是偶数，那么不可能构成回文
       如果n是奇数，但是已经有一个字符出现的次数是奇数次数了，那么如果又有一个字符是奇数次数， 就不可能构成回文。

     2.如果n是奇数，计算中间那个字符交换的次数的时候，不需要模拟把这个数移动到中间去，因为移动到中 间的话假设有一对数都在左边或者都         在右边，那么交换成回文的时候就要经过中间，就会每次把cnt多加了1，而这个1是没有必要的，因为可以所有的回文移动完了之后再把这个           独立的奇数移动过去，才能保证交换次数最少。

    3.参见大牛的博客https://blog.csdn.net/liuchuo/article/details/51990430

注意事项:

    注意分类n为奇数和偶数吧   

参考代码:

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
   int n;
   scanf("%d",&n);
   char a[10000];
   scanf("%s",a);
   int j=n-1;//j指向字符串需要交换的末尾下标
   int count=0;//记录交换次数
   int flag=0;//记录是否有字符只出现了单次，
                // 未找到相同字符串时为1
    for (int i = 0; i < j ; i++) {//i指针从头遍历到倒数第二个字符
        for (int k = j; k >=i ; k--) {//k指针从后面往前一直到i寻找和s[i]相同的s[k]
            if(k==i){//如果找不到相同的
                if(n%2==0||flag==1){//impossible的两种情况
                    printf("Impossible");
                    return 0;
                }
                flag=1;
                count+=(n-1)/2-i;  //移动到中间需要的交换次数（距离即为交换次数），
                                    // （不需要现在交换过去，最后交换）
                                    // 此时n一定为奇数，因为n是偶数已经直接输出Impossible了
            }
            else{
                if(a[k]==a[i]){
                    for(int l=k;l<j;l++){
                        swap(a[l],a[l+1]);//把s[k]换到s[j]处
                        count++;//统计交换次数
                    }
                    j--;
                    break;
                }
            }

        }
    }
    printf("%d",count);
    return 0;
}