完美的代价

发布时间: 2017年1月21日 20:31   时间限制: 1000ms   内存限制: 128M

描述

回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。

小龙龙认为回文串才是完美的。

现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。 

交换的定义是：交换两个相邻的字符 

例如mamad 

第一次交换 ad : mamda 

第二次交换 md : madma 

第三次交换 ma : madam (回文！完美！) 

输入

第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)

第二行是一个字符串，长度为N.只包含小写字母

输出

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

否则输出Impossible

样例输入1 

5mamad

样例输出1

3 贪心：

#include 
       
        int main(){    int n;    while (~scanf("%d", &n)) {        char s[8010];        scanf("%s", s);        int flag = 0, ct = 0;        int border = n - 1;        for (int i = 0; i < border; i++) {            for (int j = border; j >= 0; j--) {                if (j == i) {                    flag++;                    if (n % 2 == 0 || flag > 1) {                        printf("Impossible\n");                        goto end;                    }                    ct += n / 2 - i;                    break;                }                else if (s[i] == s[j]) {                    ct += border - j;                    for (int k = j; k < border; k++) {                        s[k] = s[k + 1];                    }                    s[border] = s[i];                    border--;                    break;                }            }        }        printf("%d\n", ct);    end:continue;    }    return 0;}