首页 > 代码库 > 蓝桥杯_基础训练_完美的代价(贪心)
蓝桥杯_基础训练_完美的代价(贪心)
基础练习 完美的代价
时间限制:1.0s 内存限制:512.0MB
问题描述
回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是:交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文!完美!)
交换的定义是:交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文!完美!)
输入格式
第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串,长度为N.只包含小写字母
第二行是一个字符串,长度为N.只包含小写字母
输出格式
如果可能,输出最少的交换次数。
否则输出Impossible
否则输出Impossible
样例输入
5
mamad
mamad
样例输出
3
题解:
用贪心,从左往右遍历字符串,对于当前字符,从右往左找相同的。
如果找到则把它移动到相应对称位置,
找不到的话如果n为奇数,不能构成回文,如果不是第一个不能匹配的也不能构成回文。
代码:
#include <iostream> #include <cstring> using namespace std; int n; int c; string a; int main() { while(cin>>n>>a) { cnt=0; c=-1; int j=n-1; bool ok=true; int sum=0; for(int i=0;i<=j;i++) //从左往右 { for(int t=j;t>=i;t--) //从右往左挨个搜索与a[i]相同的 { if(i==t) //如果没有找到 { if(n%2==0||c!=-1) //如果n为偶数,则不能成为回文,或者不是第一个不能匹配的,也不能成为回文 { ok=false; break; } //到这里的话肯定n是奇数了。 c=1; //标记第一个不能匹配的 sum+=n/2-i; //为什么不是n/2+1-i呢,因为下标从0开始的,中间的下标是n/2+1-1。 break; //一定要跳出循环,否则有可能会继续执行下面的语句,j--,就错了 } if(a[t]==a[i]) //如果找到与当前字符相同的 { for(int k=t;k<j;k++) //把它移动到对称位置。可以理解为把它后面的字符挨个往前移动一位。然后把结尾下标j--。效果相同 a[k]=a[k+1]; sum+=j-t; //计算步数 j--; //结尾下标往前移动一位 break; } } if(!ok) break; } if(!ok) cout<<"Impossible"<<endl; else cout<<sum<<endl; } return 0; }
蓝桥杯_基础训练_完美的代价(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。