思路

（1）Impossible 的两种情况：

• n为奇数时，如果已经有一个字符出现的次数为奇数，还找到了一个字符出现的次数为奇数，那么就不能构成回文串；
• n为偶数时，只要找到有一个字符出现的次数为奇数，那么就不能构成回文串。

（2）题目中要求输出最小的交换次数，那么怎样才能保证交换次数最小呢？

如果 n 为偶数，那么从第一字符开始，从后往前找第一个和它相同的字符，如果找了，就将找到的字符交换到最后一个位置，在下一次遍历时，就可以不用管刚才已经交换好的那来两个字符；下一次从第二个字符开始，从倒数第二个字符开始遍历，执行和上述相同的操作；

如果 n 为奇数，在字符串的某一个位置找到了那个出现次数为奇数的字符，我们不必将次字符现在就交换到中间位置，而是先计算它到中间位置需要交换的次数，然后累加到 cnt 中，将剩下的字符都交换到对称后，再交换这个字符即可。

试着想一想，如果第一个字符就为出现次数为奇数的字符，那么将它交换到中间位置，接下来交换其他字符时，每次的交换次数都会多一次。这其实是一种普遍的规律。

AC代码

#include <iostream>
using namespace std;
int main()
{
    int n, cnt = 0, oddNum = 0;
    cin >> n;
    string s;
    cin >> s;
    int end = n - 1;    //字符串最后一个字符
    for (int i = 0; i < end; i++)//从第一个字符到倒数第二个字符遍历
    {
        for (int j = end; j >= i; j--)//从最后一个开始，到第i个字符，寻找与s[i]相同的字符
        {
            if (i == j)       //如果没找到
            {
                if (n % 2 == 0 || oddNum == 1)  //不可能的两种情况
                {
                    cout << "Impossible";
                    return 0;
                }
                oddNum = 1;            //找到一个字符出现的次数为奇数
                cnt += n / 2 - i;    //将次字符交换到中间位置的次数
            }
            else if (s[i] == s[j])    //如果找到了，将s[j]交换到s[end]位置
            {
                for (int k = j; k < end; k++)    //交换相邻两个位置的字符
                {
                    swap(s[k], s[k+1]);
                    cnt++;
                }
                end--;                //末尾递减
                break;                //开始从i+1处重复操作
            }
        }
    }
    cout << cnt;
    return 0;
}

不想多说。先把字符分离了ASCLL表会对应一个，值然后 开始证明 引理1：交换ci时只会改变ci在除ci以外的所有元素的相对位置 可理解为一个序列 a1 a2 a3 a4 ... an 我们改变交换a3 除a3以外的序列为a1，a2，a4...an; 我们向右交换k次 即a3 插在 了 a（3+k）的右侧 a1，a2，a4，... ak，ak+1，ak+2，ak+3，a3... an; 并且发现交换的次数就是移动的距离。 引理2：当存在相等的数时，不交换其相对位置。 c1,c2...,ci,...,cj,...,cn ci =cj (i < j) 假设i，j最终位置在k,n-k(k <= n/2)回文性质 利用引理1可得即证明方程 |k-i| + |n-k-j| < |k-j| + |n-k-i| 自己分类讨论吧 六种情况 i < j < k i <k < j < n-k i < k < n-k < j k < i < j < n-k k < i < n-k < j k < n-k < i < j 其实动动脑子感觉一下就能明白，我交换相对位置不就比不交换至少多一次吗，一个交换了，一个没交换 最后我们以引理2为原则，从左边开始，保证不改变数字的相对位置 选中第i个数，从右往左 从右往左从右往左 找到第一个与他相等的数，移到n-i的位置上去 这样n = 2k的情况结束了 那n = 2k + 1咋办 可以这么想，出现在中间那个数之前，我们按原来老方案实行 当我们找到中间这个数了，左边已经结束了，不会在改了，右边可以先跳过这个数，进行排序，最后它移到中间。这样一定不会出现交换过来又换回去的操作。 代码贴了。

#include
using namespace std;
int n,p,ans;
string s;
int t[256],c[8005];
int main()
{
cin >> n >> s;
for(int i=0; i<n ;i++)
{
t[s[i]]++;
c[i+1] = s[i];
}
for(int i=0; i <= 255; i++)
{
if(t[i] % 2 == 1)
{
p++;
}
}
if(p > 1)
{
cout << "Impossible";
return 0;
}
int sp=0;
for(int i=1; i<= n/2 ;i++)
{
if(t[c[i]] == 1)
{
ans += abs(n/2+1 - i);
sp=1;
continue;
}
int k;
for(int j=n-i+1+sp; j >= i+1;j--)
{
if(c[i] == c[j])
{
ans += n-i+1 - j+sp;
k = j;
break;
}
}
for(int j=k; j <= n-i+1+sp; j++)
{
c[j] = c[j+1];
}
c[n-i+1+sp] = c[i];
t[c[i]] -= 2;
}
cout << ans;
return 0;
}

谁会拒绝一个脾气又好，又能耐心指出错误的面条老师呢

这题做的时候就小错不断

最初我的策略：偶数个字符就从右往左遍历最后找出最优解（但是题面上的最少个人感觉纯属唬人）

主要问题一直处在奇数个上的时候，本来策略变成了

找到应该属于最中间的数直接挪过去，但是一直不行，后来面条老师指出了双指针的算法

然后就AC了(((

真的感谢老师，也感谢老师没脑淤血吧

完整代码

#include<bits/stdc++.h>
using namespace std;
int n , ans ;
char a[ 8001 ] ;
int b[ 26 ] ;
int flag ;
int main()
{
    ios::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cin >> n ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        cin >> a[ i ] ;
        b[ a[ i ] -'a' ] ++ ;
    }
    for( int i = 0 ; i <= 25 ; i ++ )
    {
        if( b[ i ] % 2 == 1 ) flag ++ ;
    }
    if( flag > 1 or ( flag % 2 == 1 and n % 2 == 0 ) )
    {
        cout << "Impossible" ;
        return 0 ;
    }
    int l = n ;
    for( int i = 1 ; i < l ; i ++ )
    {
        for( int j = l ; j >= i ; j -- )
        {
            if( j == i )
            {
                ans += n / 2 + 1 - i ;
            }
            else if( a[ j ] == a[ i ] )
            {
                for( int k = j + 1 ; k <= l ; k ++ )
                {
                    swap( a[ k ] , a[ k - 1 ] ) ;
                    ans ++ ;
                }
                l -- ;
                break ;
            }
        }
    }
    cout << ans ;
    return 0;
}