试题 基础练习 完美的代价

问题描述

　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)

输入格式

　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母

输出格式

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

样例输入

5
mamad

样例输出

3

#include<iostream>
using namespace std;

int change(char str[], char special, int len) {
	int i, j, k, count = 0;

	for (i = 0; i < len / 2; i++) {
		if (str[i] == special) {
			for (j = i; j < len - i - 1; j++) {
				if (str[j] == str[len - i - 1])
					break;
			}

			count += j - i;

			for (k = j; k > i; k--) {
				str[k] = str[k - 1];
			}

			str[i] = str[len - 1 - i];
		} else {
			for (j = len - 1 - i; j >= i; j--) {
				if (str[i] == str[j])
					break;
			}

			count += len - 1 - i - j;

			for (k = j; k < len - 1 - i; k++) {
				str[k] = str[k + 1];
			}

			str[len - i - 1] = str[i];
		}
	}

	return count;
}

int main() {
	char str[8001] = { 0 }, special;
	int N, num[26] = { 0 }, i, j, k = 0;
	cin >> N;
	
	cin >> str;

	for (i = 0; i < N; i++) {
		j = str[i] - 'a';
		num[j]++;
	}

	for (j = 0; j < 26; j++) {
		if (num[j] % 2 != 0) {
			k++;
			special = j + 'a';
		}
	}

	if (k >= 2) {
		cout << "Impossible" << endl;
	} else {
		cout << change(str, special, N);
	}

	return 0;
}

总结：

重点是统计交换次数，因为要是回文数，所以要满足最多只能有一个字母出现的次数是奇数次，这里用special来记录那个特殊的字母（如果有两个及以上的字母出现奇数次，就不可能构成回文）

因为回文的对称性，所以只需要找前一半的字母来就可以

接下来其实就是找两个相同字母出现的位子，然后用靠后的位子减去前面的位子，得到的结果就是交换的次序

这里找相同字母分开一下，如果是那个特殊字母（因为它是奇数次序），则从这个特殊字母开始，往后继续找，如果不是这个字母，就可以从后面往前面去找

找完之后就要把两个相同字母排在对称位子，同理，因为找字母的时候，分成了两种找法，那么交换的时候，也是不同的派法