harumakigohan686

題目描述：

回文串，是一種特殊的字符串，它從左往右讀和從右往左讀是一樣的。崔學(xué)長認(rèn)為回文串才是完美的（但呂學(xué)弟不這樣認(rèn)為）。現(xiàn)在給你一個串，它不一定是回文的，請你計算最少的交換次數(shù)使得該串變成一個完美的回文串。

交換的定義是：交換兩個相鄰的字符

例如mamad

第一次交換 ad : mamda

第二次交換 md : madma

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

輸入格式

第一行是一個整數(shù)N，表示接下來的字符串的長度(N <= 8000)

第二行是一個字符串，長度為N.只包含小寫字母

輸出格式

如果可能，輸出最少的交換次數(shù)。

否則輸出Impossible

解題思路

首先我們要明白回文字符串的具體形成規(guī)律：當(dāng)字符串中，字符的個數(shù)是奇數(shù)的超過1個時，不能變成完美回文串。比如：字符串a(chǎn)ddbbccc，a有1個，b有2個，c有3個，d有2個。其中，a和c的個數(shù)是奇數(shù)，所以不能變成完美回文串。（通過這個來判斷是不是能形成）

然后就是交換的方面，本人提供兩種解法（其實(shí)都是在那個判斷是否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)//表示沒有符合條件的字符，該字符出現(xiàn)次數(shù)是奇數(shù)
            {
                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個小寫字母在字符串中分別出現(xiàn)了多少次
	   b[j]++; 
   } 
   for(j=0;j<26;j++)
   { 
       if(b[j]%2!=0)   //判斷有幾個字符在字符串中出現(xiàn)了奇數(shù)次 
	   { 
	       k++; 
		   x=j+'a';
		   
	  } 
   } 
   if(k>=2) 
       printf("Impossible\n"); 
   else 
       printf("%d\n",changes(s,x,n));  //調(diào)用交換字符函數(shù)
 
   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是字符串中唯一一個出現(xiàn)奇數(shù)次的字符
	   { 
	       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; 
}