完美的代价解答
完美的代价 回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。有人认为回文串是一种完美的字符串。现在给你一个字符串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个回文串。这里的交换指将字符串中两个相邻的字符互换位置,例如所给的字符串为mamad,第一次交换ad,得到mamda;第二次交换md,得到madma;第三次交换ma,得到madam (回文!完美!
5 mamad 3
|
6 aabbcd Impossible |
#include <iostream>
using namespace std;
int main()
{
int N; // 字符串长度
cin >> N;
char s[8001] = {0}; // 保证可存下结尾的'/0'
cin >> s;
// 判断是否可变为回文串
int b[26] = {0}; // 记录'a'~'z'出现的次数
for (int i = 0; i < N; i++)
b[s[i] - 'a']++; // 相应字母出现次数加一
int odd = 0; // 有多少个字母出现奇数次
char charodd = '/0'; // 出现奇数次的字母
for (int i = 0; i < 26; i++)
if (b[i] % 2 == 1) // b[i]是奇数
{
odd++;
charodd = i + 'a'; // 记录该字母
}
if (odd > 1)
cout << "Impossible" << endl; // 输出
else
{
int change = 0; // 交换次数
for (int i = 0; i < N/2; i++) // 依次考虑左侧的字母
{
if (s[i] == charodd) // 是charodd,转而考虑右侧字母
{
int j = 0;
for (j = i; j <= N-i-1; j++) // 从左侧该位置开始,找相同字母
if (s[j] == s[N-i-1]) // 找到
break;
change += j - i; // 需要j-i次移动可到左侧位置
for (int k = j; k > i; k--) // 实现字母的移动
s[k] = s[k-1];
s[i] = s[N-i-1];
}
else // 考虑左侧字母
{
int 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 (int k = j; k < N-i-1; k++) // 实现字母的移动
s[k] = s[k+1];
s[N-i-1] = s[i];
}
}
cout << change << endl; // 输出
}
return 0;
}
更多推荐
所有评论(0)