ACM模版

描述

题解

这个题一开始想岔了，一说交换最少次数使序列怎么样，我就想到了最少交换次数使序列有序的经典算法，想着可能是这个经典算法的一个变种，后来发现并不是这样的，其实只是一个简单的贪心就能解决的问题。

先从左往右选取左侧元素，然后从右侧开始往左侧查找匹配元素，每次找到后都移动到对称位置，累加移动次数即可……典型的贪心。

这个题远远没有想象中那么麻烦~~~

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 8888;

int n;
char s[MAXN];

int main()
{
    scanf("%d%s", &n, s);

    int sum = 0, flag = 1, tag = -1;
    int len = n - 1;
    for (int i = 0; i < len; i++)
    {
        for (int j = len; j >= i; j--)
        {
            if (j == i)
            {
                if (n % 2 == 0 || tag != -1)
                {
                    flag = 0;
                    break;
                }
                tag = 1;
                sum += n / 2 - i;
                break;
            }
            if (s[j] == s[i])
            {
                for (int t = j; t < len; t++)
                {
                    s[t] = s[t + 1];
                }
                sum += len - j;
                len--;
                break;
            }
        }
        if (!flag)
        {
            break;
        }
    }

    if (!flag)
    {
        printf("Impossible\n");
    }
    else
    {
        printf("%d\n", sum);
    }

    return 0;
}