回文串是一種特殊的字符串，它從左往右讀和從右往左讀是一樣的，有人認(rèn)為回文串是一種完美的字符串。現(xiàn)在給你一個字符串，它不一定是回文的，請你計(jì)算最少的交換次數(shù)使得該字符串變成一個回文串。這里的交換指將字符串中兩個相鄰的字符互換位置。 例如所給的字符串為”mamad”，第一次交換a和d，得到”mamda”，第二次交換m和d，得到”madma”；第三次交換最后面的m和a，得到”madam”。

輸入格式:
第一行是一個整數(shù)N（N <= 80），表示所給字符串的長度，第二行是所給的字符串，長度為N且只包含小寫英文字母。

輸出格式:
如果所給字符串能經(jīng)過若干次交換變成回文串，則輸出所需的最少交換次數(shù)；否則，輸出Impossible。

輸入樣例:
5
mamad
輸出樣例:
3
這道題剛開始寫的時候是不會做的，然后就去參考別人的代碼，發(fā)現(xiàn)都是說貪心算法的。
知道貪心算法這么個算法，但是卻沒有去學(xué)習(xí)過，結(jié)果到這就去補(bǔ)習(xí)了。
這邊還是建議去學(xué)習(xí)一下貪心算法的思路，再來配合代碼理解（還是很有用的）

#include<stdio.h> #include<math.h>int check(char *str,int len);//判斷是否可以回文 int swap(char *str,int len);//記錄交換次數(shù)int main(){int n;scanf("%d",&n);char str[n];scanf("%s",str);if(check(str,n)){printf("%d",swap(str,n));}else{printf("Impossible");} }int check(char *str,int len){int flag;int a[len],count=0,c=0;for(int i=0;i<len;i++){a[i]=0;}for (int i=0;i<len;i++){for (int j=0;j<len;j++){if(str[i]==str[j]){a[count]++;}}count++;}for(int i=0;i<len;i++){if(a[i]%2==1){c++;}}if(c>1)flag=0;else flag=1;return flag; }int swap(char *str,int len){int mid=(len+1)/2;int count=0,xb,flag;for(int i=0;i<mid;i++){xb=-1;for(int j=i+1;j<len;j++){if(str[i]==str[j]){xb=j;break;}}if(xb==-1){//這里偷了個小懶，并沒有把他移動到中間（但是后面的交換環(huán)節(jié)會將使單個的字符移動到中間）count+=fabs(mid-1-i);flag=i;}else{for(int k=xb;k<len-i-1;k++){char temp=str[k];str[k]=str[k+1];str[k+1]=temp;count++;}}}return count; }

總結(jié)

以上是生活随笔為你收集整理的综合程序设计 7-4 完美的代价 (40分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。