蓝桥---完美的代价（swap成回文串、贪心）

Description

回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。

现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)

Input

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

Output

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

Sample Input

5
mamad

Sample Output

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const double eps =1e-8;
16 const int mod=1e9+7;
17 const int maxn=1e6+10;
18 using namespace std;
19 
20 string str;
21 
22 int main()
23 {
24     #ifdef DEBUG
25     freopen("sample.txt","r",stdin);
26     #endif
27     
28     int n;
29     cin>>n;
30     cin>>str;
31     int ans=0;
32     int flag=1;
33     int num=0;//无法匹配的字符的个数 
34     int R=n-1;//移动的终点位置 
35     for(int i=0;i<=R;i++)//i从前往后遍历
36     {
37         int pos=i;
38         for(int j=R;j>=i;j--)//j从后往前遍历
39         {
40             if(str[i]==str[j])
41             {
42                 pos=j;
43                 break;
44             }
45         }
46         if(i==pos)//找到自己了，说明无配对
47         {
48             if(n%2!=0&&num==0)//奇数串只能有一个无匹配字符
49             {
50                 num++;
51                 ans+=n/2-i;
52         //这里先把它放在这里，若是把它先移到中间，其他人配对时，就可能会经过他，所以最后再把他放中间
53             }
54             else//偶数串不能有无匹配字符， 
55             {
56                 flag=0;
57                 break;
58             }
59         }
60         else
61         {
62             for(int k=pos;k<R;k++)
63             {
64                 swap(str[k],str[k+1]);
65                 ans++;
66             }
67             R--;//匹配下一个
68         }
69     }
70     if(flag==0) printf("Impossible
");
71     else printf("%d
",ans);
72     
73     return 0;
74 }