本文共 843 字，大约阅读时间需要 2 分钟。

问题描述

　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。

输入格式

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

输出格式

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

样例输入

5

样例输出

3

【思路】

先统计给出的字符串中每个字符出现的个数，，如果奇数次字符的个数大于1，直接输出Impossible，，

从第一个字符开始，，从后往前找和它匹配的字符，，如果没找到，，那么这个字符移动到中间位置，；；

如果找到了，，把这个对称的字符移动到当前字符的对称位置，，每移动一次，，就加1，

最后输出cnt。。

#include 
   
    using namespace std;int a[26];int main(){    ios::sync_with_stdio(false);    int i,j,k,n,sum=0,cnt=0;    string s;    cin>>n>>s;    int temp=n-1;    for(i=0;i
    
     1)        {            cout<<"Impossible"<
     
      =i;j--)        {            if(j==i)                cnt+=n/2-i;            else if(s[i]==s[j])            {                for(k=j;k
     
    
   

转载地址：http://uxyzi.baihongyu.com/