解题思路:
1.impossible的情况:如果有一个字符出现的次数是奇数次数,而且n是偶数,那么不可能构成回文
如果n是奇数,但是已经有一个字符出现的次数是奇数次数了,那么如果又有一个字符是奇数次数, 就不可能构成回文。
2.如果n是奇数,计算中间那个字符交换的次数的时候,不需要模拟把这个数移动到中间去,因为移动到中 间的话假设有一对数都在左边或者都 在右边,那么交换成回文的时候就要经过中间,就会每次把cnt多加了1,而这个1是没有必要的,因为可以所有的回文移动完了之后再把这个 独立的奇数移动过去,才能保证交换次数最少。
3.参见大牛的博客https://blog.csdn.net/liuchuo/article/details/51990430
注意事项:
注意分类n为奇数和偶数吧
参考代码:
#include <iostream> #include <cstdio> using namespace std; int main() { int n; scanf("%d",&n); char a[10000]; scanf("%s",a); int j=n-1;//j指向字符串需要交换的末尾下标 int count=0;//记录交换次数 int flag=0;//记录是否有字符只出现了单次, // 未找到相同字符串时为1 for (int i = 0; i < j ; i++) {//i指针从头遍历到倒数第二个字符 for (int k = j; k >=i ; k--) {//k指针从后面往前一直到i寻找和s[i]相同的s[k] if(k==i){//如果找不到相同的 if(n%2==0||flag==1){//impossible的两种情况 printf("Impossible"); return 0; } flag=1; count+=(n-1)/2-i; //移动到中间需要的交换次数(距离即为交换次数), // (不需要现在交换过去,最后交换) // 此时n一定为奇数,因为n是偶数已经直接输出Impossible了 } else{ if(a[k]==a[i]){ for(int l=k;l<j;l++){ swap(a[l],a[l+1]);//把s[k]换到s[j]处 count++;//统计交换次数 } j--; break; } } } } printf("%d",count); return 0; }
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:483 |
WU-整数平均值 (C++代码)浏览:1245 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:506 |
用筛法求之N内的素数。 (C语言代码)浏览:650 |
【明明的随机数】 (C语言代码)浏览:787 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:373 |
母牛的故事 (C语言代码)浏览:551 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1466 |
1050题解(结构体数组与结构体指针的使用)浏览:1109 |
C二级辅导-统计字符 (C语言代码)浏览:481 |