试题 基础练习 完美的代价
2023-09-14 09:14:25 时间
试题 基础练习 完美的代价
资源限制
内存限制:512.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
问题描述
回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是:交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文!完美!)
输入格式
第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串,长度为N.只包含小写字母
输出格式
如果可能,输出最少的交换次数。
否则输出Impossible
样例输入
5
mamad
样例输出
3
提交代码:
#include<iostream>
using namespace std;
int main()
{
int n, flag=0, swap_cnt=0;
cin>>n;
string str;
cin>>str;
for(int i=0; i<n-1; i++)
{
for(int j=n-1; j>=i; j--) //从右往左进行匹配
{
if(j==i) //没有匹配的字母
{
if(flag==1||str.size()%2==0)
{
cout<<"Impossible"<<endl;
return 0;
}
flag=1;
swap_cnt+=str.size()/2-i; //计算单个字母的交换次数
}
else if(str[i]==str[j]) //匹配到位置时
{
for(int k=j; k<n-1; k++)
{
swap(str[k], str[k+1]); //将位置进行交换
swap_cnt++; //累计交换次数
}
n--; //每搜索完一次后,相应匹配的字母放在最右边。下次搜索从n-1的位置,从右往左匹配。
break;
}
}
}
cout<<swap_cnt<<endl;
return 0;
}
相关文章
- SQL Server调优系列基础篇(并行运算总结)
- C/C++基础讲解(八十二)之常见试题解答篇(方差运算/级数运算/输出素数/素数题)
- C/C++基础讲解(七十一)之常见试题解答篇(求解符号方程/计算标准差/求取符合特定要求的素数)
- C/C++基础讲解(七十)之常见试题解答篇(水果拼盘/小孩吃梨/删除字符串中的特定字符)
- python的基础试题
- 试题 基础练习 数列特征
- 试题 基础练习 杨辉三角形
- 试题 基础练习 特殊的数字
- 试题 基础练习 十六进制转十进制
- 试题 基础练习 十六进制转八进制
- 试题 基础练习 Sine之舞
- 试题 基础练习 2n皇后问题
- 试题 基础练习 闰年判断
- 试题 基础练习 01字串
- 试题 基础练习 数列特征
- 试题 基础练习 数列排序