蓝桥杯练习系统：基础练习 完美的代价

问题描述

　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)

输入格式

　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母

输出格式

　　如果可能，输出最少的交换次数。
　　否则输出Impossible

样例输入

5
mamad

样例输出

3

#include <iostream>
using namespace std;
int main()
{
    int N;     // 字符串长度
    cin >> N;
    char s[8001] = {0};  // 保证可存下结尾的'/0'
    cin >> s;

    // 判断是否可变为回文串
    int b[26] = {0};   // 记录'a'~'z'出现的次数
    for (int i = 0; i < N; i++)
        b[s[i] - 'a']++;  // 相应字母出现次数加一
    int odd = 0;    // 有多少个字母出现奇数次
    char charodd = '/0';  // 出现奇数次的字母
    for (int i = 0; i < 26; i++)
        if (b[i] % 2 == 1)  // b[i]是奇数
        {
            odd++;
            charodd = i + 'a'; // 记录该字母
        }
    if (odd > 1)//不可变为回文串（当odd为0或1时，都可以）
        cout << "Impossible" << endl;
    else
    {
        int change = 0;     // 交换次数
        for (int i = 0; i < N/2; i++) // 依次考虑中点左侧的字母
        {
            if (s[i] == charodd)  // 是charodd，转而考虑右侧字母
            {
                int j = 0;
                for (j = i; j <= N-i-1; j++) // 从左侧该位置开始，向右直至右侧对称位置，找相同字母
                    if (s[j] == s[N-i-1])  // 找到
                        break;
                change += j - i;    // 需要j-i次移动可到左侧位置
                for (int k = j; k > i; k--)  // 实现字母的移动
                    s[k] = s[k-1];
                s[i] = s[N-i-1];//为了省事，并非两两互换，只是右边赋为左边的值，所以最后将i位赋值
            }
            else  // 考虑左侧字母
            {
                int j = 0;
                for (j = N-i-1; j >= i; j--) // 从右侧对称位置开始，向左直至i位（向右是排序好了的），找相同字母
                    if (s[j] == s[i])   // 找到
                        break;
                change += N-i-1 - j;   // 需要N-i-j-j次移动可到右侧位置
                for (int k = j; k < N-i-1; k++) // 实现字母的移动
                    s[k] = s[k+1];
                s[N-i-1] = s[i];
            }
        }
        cout << change << endl;     // 输出
    }
    return 0;
}