交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)
第二行是一个字符串，长度为N.只包含小写字母
否则输出Impossible
mamad
解决办法：
一、输出Impossible
不必考虑是字符串长度为奇数偶数
只需考虑，出现次数为奇数的字母个数，若个数 等于或大于2 ，则不能构成回文
当所有字母次数都为偶数时，一定可以构成回文
如：
abbchca
h出现次数为1，且只有h出现次数为奇数，能构成回文
abbbchca
b出现次数为3，h为1，则有两个奇数字母，不能构成回文
abbchhca
所有字母出现次数都为偶数，必定可以构成回文
二、能构成回文
1、注意
交换的定义是：交换两个相邻的字母
2、要保证交换次数最少，则每个字母都是单向移动。
3、从外部开始向内，因为内部的改变不影响外部已排好的序列，不会产生重复。
4、找到中点(l+1)/2 （l为字符串长度，l从1开始）：i<(l+1)/2，i从0开始，这个可以自己试一下
从左边第一个作为定点（不移动位置）开始，查找自右第一个往左找到相同字母，将相同字母移动到回文对应位置，记录交换次数
从左边第二个作为定点开始，查找自右第二个往左找到相同字母，将相同的字母移动到对应的位置，记录交换次数
以此类推。
注意：在这个过程中不改变外部排好的序列，外部已排好的下次查找可直接略过。（见3）
如图：最少交换次数为3
5、如果存在字母在未排序内找不到相同字母（即单个的奇数字母），或者单个的字母出现在字符串中点左边（在右边时会因为各个字母的交换而最后被换到中点位置去）
//比如h出现3次，则在字符串中最靠左与最靠右（交换次数最少）的h可配成一对回文，剩下一个放中点位置
先不移动，计算该字母到中点所需交换次数，然后将它忽略，继续从它下个字母进行回文排列
注意：
此时对应位置发生改变
//比如一个长度为7的字符串，若左边第一个字母即为单个的奇数字母，那么左边第二个字母对应的回文的位置为右边第一个
当后面字符串形成回文时，再移动该奇数字母至中点位置
//若先移动，则每个字母排序时交换的次数+1
如图：最少交换次数为6
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
int l;
scanf("%d",&l);
char a[l];
//清除一个无效字符---回车
getchar();
//输入字符串a
gets(a);
//数组b的26个变量分别对应26个字母
int b[26]={0},i;
//统计字符串中各字母出现的次数
for(i=0;i<l;i++)
{
b[a[i]-'a']++;
}
//统计出现次数为奇数的字母个数
int k=0;
for(i=0;i<26;i++)
{
if(b[i]%2!=0)
k++;
}
//若存在2个及以上次数为奇数的字母
if(k>=2)
{
printf("Impossible");
exit(0);
}
else
{
//h计形成回文所需次数，
//m计奇数字符串时，奇数字母到达中点位置所需次数
//g用于改变交换位置长度
int h=0,g=l,m=0;
for(i=0;i<(l+1)/2;i++)
{
int j;
//查找是否存在不同位置的相同字母
for(j=g-1;j>i;j--)
{
//存在
if(a[i]==a[j])
{
while(j<g-1)
{
//交换至对应位置
char t;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
j++;
h++;//记录次数
}
g--;
break;
}
}
//不存在，则为奇数字母
if(j==i)
m=(l-1)/2-i;
}
printf("%d",h+m);
}
return 0;
}
代码应该是存在...不足的呃，但是大概思路是这样子
如有误，或者是说不清楚的地方，欢迎大家告诉我~