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

问题描述

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

输入格式

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

输出格式

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

样例输入

5
mamad

样例输出

3

#include<iostream>
using namespace std;

int n, t = 0, g = 0;
char *b;
//判断是否有可能移动成回文数；
int huiwen(char a[]) {
    int dange = 0;
    for(int i = 0; i < n; i ++) {
        int flag = 1;
        for (int p = 0; p < i; p ++) {
            if(a[p] == a[i]) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            int sum = 1;
            for (int j = i + 1;j < n;j ++) {
                if (a[j] == a[i])
                    sum ++;
            }
            if (sum % 2){
                dange ++;
                if (dange >= 2) {
                    return 0;
                }
            }
        }
    }
    return 1;
}
void swap(char *a,char *d) {
    //交换一次两个相临的字符；
    char c = *a;
    *a = *d;
    *d = c;
    g ++;
}
int  main()
{
    cout << "请输入字符串的长度:" << endl;
    cin >> n;
    b = new char[n];
    cout << "请输入字符串:" << endl;
    cin >> b;
    if (! huiwen(b))
        cout << "Impossible" << endl;
    else {
        for(int i = 0;i < (n - 1) / 2; i ++) {
            if (b[n - 1 - t] != b[i]) {
                for(int j = n - 1 - i; j > i; j --)
                    if(b[i] == b[j]) {
                        t ++;
                        for(int p = j;p < n - t; p ++) {
                            char *pa,*pb;
                            pa = &b[p];
                            pb = &b[p + 1];
                            swap(pa,pb);
                        }
                        break;
                    }
            }
            else t ++;
        }
        for(int q = 0;q < (n - 1) / 2; q ++) {
            int z = n - 1 - q;
            if(b[q] != b[z]) {
                char *pa,*pb;
                pa = &b[q];
                pb = &b[q + 1];
                swap(pa,pb);
            }
        }
        cout << "最少移动次数：" << g << endl;
        cout << "经过移动后的回文串：" << endl;
        cout << b;
        cout << endl;
    }
    return 0;
}

别直接用，删去那些提示性的语句才可以。

因为是别人写的，我就不好意思注释了，大家自己体会吧。

很有意思的代码