首页 > 代码库 > 完美代价
完美代价
问题描述
回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是:交换两个相邻的字符
例如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
c代码如下
#include<stdio.h> int changes(char s[],char x,int n); char x=‘0‘; int main() { int n,i,k=0,b[26]={0},j; char y,s[8001]={0}; scanf("%d",&n); getchar(); for(i=0;i<n;i++) scanf("%c",&s[i]); for(i=0;i<n;i++){//数组 j=s[i]-‘a‘;将字符转换成ACS码,b[]统计各个字母的个数 j=s[i]-‘a‘; b[j]++; } for(j=0;j<26;j++){/*如果所有字母出现偶数次,那么该字符串可以进行字符间的交替,成为回文串。即(b[j]%2!=0);*/ if(b[j]%2!=0){//统计共有几个奇数字母 k++; x=j+‘a‘;//x是奇数字母(一个奇数字母的时候有用) } } if(k>=2)/*如果有两个字母或者两个字母以上出现了奇数次,那么该字符串不能通过字符间的交替成为回文串。*/ printf("Impossible\n"); else printf("%d\n",changes(s,x,n)); return 0; } int changes(char s[],char x,int n)//统计交换次数 { int i,change=0,j,k; for(i=0;i<n/2;i++){ if(s[i]==x){//当遍历到奇数字母时,可以以回文对应位置的字母来交换 for(j=i;j<n-i-1;j++) if(s[n-i-1]==s[j]) break; change+=j-i; for(k=j;k>i;k--) s[k]=s[k-1]; s[i]=s[n-i-1]; } else//否则,以左边字母进行交换次数统计 { for(j=n-i-1;j>=i;j--) if(s[i]==s[j]) break; change+=n-i-1-j; for(k=j;k<n-i-1;k++) s[k]=s[k+1]; s[n-i-1]=s[i]; } } return change; }
总结
这道题一开始拿上手的时候,确实不知怎么办。而且说要用到贪心算法,但是我看了半天都不知道怎么用到。但是我知道他肯定会有一种情况,输出impossible,所以我就写了一条语句,拿了10分。其实多找几个例子,列出多种情况,然后自己解决,完了自己找规律,就发现其算法了。
知道算法了,就该编码实现。这个时候,你就按照一种情况,一个流程走下去,一种情况的解决完了,就写另外一种情况的程序。
程序写完以后,就可以看程序,总结程序规律。总结出来调试,测试。ok,大功告成。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。