蓝桥杯 完美的代价

问题描述

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

输入格式

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

输出格式

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

样例输入

5
mamad

样例输出

3

#include <bits/stdc++.h> 
using namespace std; 
int num[26]; //存储每个字母出现的个数 
int main() { 
    int n; 
    cin >> n;
    string a;  
    cin >> a;
    int flag = 0; //出现次数为奇数的字母的个数 
    int cnt = 0; //交换次数 
    int temp = n - 1; //字符串最后一个字母的下标 
    for(int i = 0; i < n; i++) { //遍历字符串，计算出现次数 
        num[a[i] - 'a']++; 
    } 
    for(int i = 0; i < 26; i++) { //判断 
        if(num[i] % 2 != 0) { 
            flag++; 
        } 
    } 
    if ((n % 2 == 0 && flag >= 1) || (n % 2 == 1 && flag >= 2)) {
        cout << "Impossible" << endl;
        return 0;
    }
    for(int i = 0; i <= temp; i++) { 
        for(int j = temp; j >= i; j--) { 
            if(i >= j) { 
                cnt += n / 2 - i; 
            } else if(a[i] == a[j]) { 
                for(int k = j; k < temp; k++) { 
                    swap(a[k], a[k + 1]); 
                    cnt++; 
                } 
                temp--; 
                break; 
            } 
        } 
    } 
    cout << cnt << endl; 
    return 0; 
}