问题描述
　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)
输入格式
　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母
输出格式
　　如果可能，输出最少的交换次数。
　　否则输出Impossible
样例输入
5
mamad
样例输出
3

思路：先判断这个字符串是否可以组成一个回文字符串，然后按照每一个字母出现的次数为偶数还是奇数进行讨论。每一次都是从第一个字母开始往后进行检测，要是遇到了出现次数为1的字母，先不要动它，等到其他的字母都排完了，再直接将其放到字符串的中间即可；如果所有的字母出现次数都为偶数个，那么从字符串的最后开始往前检测，直到遇到和当前字母相同的字母，再进行位置交换。

复制代码
  1 #include<iostream>
  2 using namespace std;
  3
  4 class huiwen
  5 {
  6 public:
  7     int get_n()
  8     {
  9         cin>>n;
10         return n;
11     }
12     void get_putin()
13     {
14         cin>>putin;
15     }
16     void exchange()
17     {
18         for(int i=0;i<n;i++)
19         {
20             num[putin[i]-'a']++;
21         }
22         for(int i=0;i<26;i++)
23         {
24             if(num[i]%2!=0)
25             {
26                 t++;
27             }
28         }
29         if(t>=2)  //要是有两个或两个以上的字母出现次数为奇数，那么这个字符串不可能为回文字符串
30         {
31             cout<<"Impossible";
32             return;
33         }
34         else if(t==0)    //说明所有字母的出现次数都是偶数
35         {
36             for(int i=0;i<n/2-1;i++)
37             {
38                 flag=-1;
39                 for(int j=n-a-1;j>i;j--)
40                 {
41                     if(putin[i]==putin[j])
42                     {
43                         flag=j;
44                         break;
45                     }
46                 }
47                 char temp=putin[flag];
48                 for(int m=flag;m<n-1-a;m++)
49                 {
50                     putin[m]=putin[m+1];
51                 }
52                 putin[n-1-a]=temp;
53                 time=time+(n-1-a-flag);   //计算移动次数
54                 a++;
55             }
56         }
57         else if(t==1)
58         {
59             for(int i=0;i<=n/2;i++)
60             {
61                 flag=-1;
62                 for(int j=n-a-1;j>i;j--)
63                 {
64                     if(putin[i]==putin[j])
65                     {
66                         flag=j;
67                         break;
68                     }
69                 }
70                 if(flag==-1)   //遇到出现次数为1次的字母了
71                 {
72                     time=time+(n/2-i);
73                 }
74                 else
75                 {
76                     char temp=putin[flag];
77                     for (int m = flag; m < n - 1 - a; m++)
78                     {
79                         putin[m] = putin[m + 1];
80                     }
81                     putin[n - 1 - a] = temp;
82                     time = time + (n - 1 - a - flag);   //计算移动次数
83                     a++;
84                 }
85             }
86         }
87         cout<<time;
88         return;
89     }
90 private:
91     int n;    //输入字符串所含字母个数
92     char putin[8001];   //输入字符串
93     int num[26]={0};   //一共有26个字母，判断每一个字母的出现次数
94     int t=0;   //整个字符串里面有多少个出现次数为奇数的字母
95     int a=0;   //表示已经处理到第a个字母
96     int flag;  //用flag来记录后一半字符串匹配的最近的字母下标
97     int time=0;  //用来计算移动字母的次数
98 };
99
100 int main(void)
101 {
102     huiwen string;
103     string.get_n();
104     string.get_putin();
105     string.exchange();
106     return 0;
107 }
复制代码
注意：题目中的交换的意思和一般的交换意思不一样，这里只能挨个地进行交换，而一般所说的交换是直接将两个字符进行对调，所以计算交换次数的时候不能只算一次。

更多讯息欢迎添加小优：DKA-2018