完美的代价

野性酷女 2022-08-01 02:53 163阅读 0赞

问题描述

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

交换的定义是：交换两个相邻的字符

例如mamad

第一次交换 ad : mamda

第二次交换 md : madma

第三次交换 ma : madam(回文！完美！)

输入格式

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

第二行是一个字符串，长度为N.只包含小写字母

输出格式

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

否则输出Impossible

样例输入

mamad

样例输出

参考代码：

<span style="font-family:KaiTi_GB2312;">#include<stdio.h>
    int main()
    {
    	int N;     // 字符串长度
    	int change=0;//交换次数 
    	int i,j,k;
    	int odd = 0;    // 有多少个字母出现奇数次
    	char charodd = 0;  // 出现奇数次的字母
    	char s[8001] = {0};  // 保证可存下结尾的'/0'
    	int b[26] = {0};   // 记录'a'~'z'出现的次数
    	scanf("%d",&N);
    	getchar();
    	gets(s);
    	// 判断是否可变为回文串
    	for (i = 0; i < N; i++)
    		b[s[i] - 'a']++;  // 相应字母出现次数加一
    	for (i = 0; i < 26; i++)
    	if (b[i] % 2 == 1){  // b[i]是奇数
    		odd++;
    		charodd = i + 'a'; // 记录该字母
    	}
    	if (odd > 1)
    		printf("Impossible\n");//输出 
    	else{
    		for (i = 0; i < N/2; i++){ // 依次考虑左侧的字母
    			if (s[i] == charodd)  // 是charodd，转而考虑右侧字母
    			{
    				j = 0;
    				for (j = i; j <= N-i-1; j++) // 从左侧该位置开始，找相同字母
    					if (s[j] == s[N-i-1])  // 找到
    						break;
    				change += j - i;    // 需要j-i次移动可到左侧位置
    				for (k = j; k > i; k--)  // 实现字母的移动
    					s[k] = s[k-1];
    				s[i] = s[N-i-1]; 
    			}
    			else{  // 考虑左侧字母
    				j = 0;
    				for (j = N-i-1; j >= i; j--) // 从右侧对称位置开始，找相同字母
    					if (s[j] == s[i])   // 找到
    						break;
    				change += N-i-1 - j;   // 需要N-i-j-j次移动可到右侧位置
    				for (k = j; k < N-i-1; k++) // 实现字母的移动
    					s[k] = s[k+1];
    				s[N-i-1] = s[i];
    			}
    		}
    		printf("%d\n",change);//输出 
    	}
    	return 0;
    }
    </span>

测试结果：

![SouthEast][]

[SouthEast]: /images/20220731/e9277fc3057f4a54bc51ca03a5cb970b.png