解题思路:
注意事项:
参考代码:
#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.0分
7 人评分
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:470 |
C语言训练-排序问题<1> (C++代码)浏览:610 |
C语言训练-立方和不等式 (C语言代码)浏览:761 |
C语言程序设计教程(第三版)课后习题6.6 (C++代码)浏览:637 |
简单的a+b (C语言代码)浏览:620 |
出圈】指针malloc版浏览:358 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:688 |
小九九 (C语言描述,不看要求真坑爹)浏览:986 |
【偶数求和】 (C++代码)浏览:704 |
求圆的面积 (C语言代码)浏览:687 |