【题解】【比赛】完美的代价

首先是Impossible的情况
1、当N是偶数且有一个字符出现次数为奇数时那一定不可能构成回文数如adaaaa
2、当N是奇数且有两个不等的字符出现次数为奇数时页一定不可能构成回文数如abada
然后是可以移成回文数的情况

采用贪心思想，从左向右遍历当前字符串s[i]，然后从右向左遍历找到与当前字符串s[i]相等的字符串s[k]，将s[k]移到字符串末尾(彼此相邻的移动)，然后将指向末尾的指针减一。
再看s[i+1]，从右(末尾已经减一)向左遍历找到与其相同的字符再将其移到末尾，再将末尾减一，以此类推

#include<bits/stdc++.h>
using namespace std;
int n;
string s;

int main() {
    cin >> n;
    cin >> s;

    int j = n-1;
    int res = 0;	//res用来统计交换的次数
    int flag = 0;	//flag用来统计出现奇数次数的字符个数

    for(int i = 0; i < j; i++)	//i指针从头遍历到倒数第二个字符
	{
        for(int k = j; k >= i; k--)	//k指针从后面往前一直到i寻找和s[i]相同的s[k]
		{
            if(k == i)	//如果找不到相同的
			{
				flag++;
                if(n % 2 == 0 || flag == 2)	//impossible的两种情况
				{
                    cout << "Impossible"<<endl;
                    return 0;
                }               
                res += n / 2 - i;	//n为奇数时唯一一个奇数次出现的字符移到中间的次数
									//n/2-i一定大于0即这个数是在整体的左边位置，如果在右边遍历前面的i时就已经把它移到中间了，如aaaad  
            } 
			else if(s[i] == s[k])   
			{
                for(int l = k; l < j; l++) 
				{
                    swap(s[l], s[l+1]);//把s[k]换到s[j]处  
                    res++;//统计交换次数
                }
                j--;	//将一个字符调到末尾后j减一即将末尾指针往前移一位
						//方便下次交换到末尾且i和j相等时此时已经是回文数第一个for循环就结束了
                break;
            }
        }
    }
    cout << res <<endl;
    return 0;
}