蓝桥杯真题初探：CP1102. 完美的代价

题目描述：

回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。崔学长认为回文串才是完美的（但吕学弟不这样认为）。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。

交换的定义是：交换两个相邻的字符

例如mamad

第一次交换 ad : mamda

第二次交换 md : madma

第三次交换 ma : madam (回文！完美！)

输入格式

第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)

第二行是一个字符串，长度为N.只包含小写字母

输出格式

如果可能，输出最少的交换次数。

否则输出Impossible

解题思路

首先我们要明白回文字符串的具体形成规律：当字符串中，字符的个数是奇数的超过1个时，不能变成完美回文串。比如：字符串addbbccc，a有1个，b有2个，c有3个，d有2个。其中，a和c的个数是奇数，所以不能变成完美回文串。（通过这个来判断是不是能形成）

然后就是交换的方面，本人提供两种解法（其实都是在那个判断是否ok方面的两种思路）：

解题代码

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
void swap(char a,char b);
int main()
{
    long int n;
    scanf("%ld",&n);
    getchar();
    char a[8005];
    gets(a);
    int k=n-1;
    int flag=0;
   long int count=0;
    for(int i=0;i<k;i++)//从第一个开始搜索
    {
        for(int j=k;j>=i;j--)
        {
            if(j==i)//表示没有符合条件的字符，该字符出现次数是奇数
            {
                if(flag==1||n%2==0)
                {
                    printf("Impossible\n");
                    return 0;
                }
                flag=1;
                count=count+n/2-i;
            }
            else if(a[i]==a[j])
            {
                for(int u=j;u<k;u++)
                {
                    swap(a[u],a[u+1]);
                    count++;
                }
                k--;
                break;
            }
        }

    }
    printf("%ld",count);
    return 0;
}

void swap(char a,char b)
{
    char temp;
    temp=a;
    a=b;
    b=temp;
}
这里是分割线~

#include <stdio.h>
#include <stdlib.h>
 
int changes(char s[],char x,int n); 
char x='0'; 
int main(void) 
{ 
   int n,i,k=0,b[26]={0},j; 
   char s[8000]={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';  //判断26个小写字母在字符串中分别出现了多少次
	   b[j]++; 
   } 
   for(j=0;j<26;j++)
   { 
       if(b[j]%2!=0)   //判断有几个字符在字符串中出现了奇数次 
	   { 
	       k++; 
		   x=j+'a';
		   
	  } 
   } 
   if(k>=2) 
       printf("Impossible\n"); 
   else 
       printf("%d\n",changes(s,x,n));  //调用交换字符函数
 
   system("pause");
   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)    //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; 
}