用C++实现：完美的代价

问题描述

　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)

输入格式

　　第一行是一个整数n，表示接下来的字符串的长度(n <= 8000)
　　第二行是一个字符串，长度为n.只包含小写字母

输出格式

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

样例输入

5
mamad

样例输出

3

 

思路：先判断这个字符串是否可以组成一个回文字符串，然后按照每一个字母出现的次数为偶数还是奇数进行讨论。每一次都是从第一个字母开始往后进行检测，要是遇到了出现次数为1的字母，先不要动它，等到其他的字母都排完了，再直接将其放到字符串的中间即可；如果所有的字母出现次数都为偶数个，那么从字符串的最后开始往前检测，直到遇到和当前字母相同的字母，再进行位置交换。

 

  1 #include<iostream>
  2 using namespace std;
  3 
  4 class huiwen
  5 {
  6 public:
  7     int get_n()
  8     {
  9         cin>>n;
 10         return n;
 11     }
 12     void get_putin()
 13     {
 14         cin>>putin;
 15     }
 16     void exchange()
 17     {
 18         for(int i=0;i<n;i++)
 19         {
 20             num[putin[i]-'a']++;
 21         }
 22         for(int i=0;i<26;i++)
 23         {
 24             if(num[i]%2!=0)
 25             {
 26                 t++;
 27             }
 28         }
 29         if(t>=2)  //要是有两个或两个以上的字母出现次数为奇数，那么这个字符串不可能为回文字符串
 30         {
 31             cout<<"impossible";
 32             return;
 33         }
 34         else if(t==0)    //说明所有字母的出现次数都是偶数
 35         {
 36             for(int i=0;i<n/2-1;i++)
 37             {
 38                 flag=-1;
 39                 for(int j=n-a-1;j>i;j--)
 40                 {
 41                     if(putin[i]==putin[j])
 42                     {
 43                         flag=j;
 44                         break;
 45                     }
 46                 }
 47                 char temp=putin[flag];
 48                 for(int m=flag;m<n-1-a;m++)
 49                 {
 50                     putin[m]=putin[m+1];
 51                 }
 52                 putin[n-1-a]=temp;
 53                 time=time+(n-1-a-flag);   //计算移动次数
 54                 a++;
 55             }
 56         }
 57         else if(t==1)
 58         {
 59             for(int i=0;i<=n/2;i++)
 60             {
 61                 flag=-1;
 62                 for(int j=n-a-1;j>i;j--)
 63                 {
 64                     if(putin[i]==putin[j])
 65                     {
 66                         flag=j;
 67                         break;
 68                     }
 69                 }
 70                 if(flag==-1)   //遇到出现次数为1次的字母了
 71                 {
 72                     time=time+(n/2-i);
 73                 }
 74                 else
 75                 {
 76                     char temp=putin[flag];
 77                     for (int m = flag; m < n - 1 - a; m++)
 78                     {
 79                         putin[m] = putin[m + 1];
 80                     }
 81                     putin[n - 1 - a] = temp;
 82                     time = time + (n - 1 - a - flag);   //计算移动次数
 83                     a++;
 84                 }
 85             }
 86         }
 87         cout<<time;
 88         return;
 89     }
 90 private:
 91     int n;    //输入字符串所含字母个数
 92     char putin[8001];   //输入字符串
 93     int num[26]={0};   //一共有26个字母，判断每一个字母的出现次数
 94     int t=0;   //整个字符串里面有多少个出现次数为奇数的字母
 95     int a=0;   //表示已经处理到第a个字母
 96     int flag;  //用flag来记录后一半字符串匹配的最近的字母下标
 97     int time=0;  //用来计算移动字母的次数
 98 };
 99 
100 int main(void)
101 {
102     huiwen string;
103     string.get_n();
104     string.get_putin();
105     string.exchange();
106     return 0;
107 }

注意：题目中的交换的意思和一般的交换意思不一样，这里只能挨个地进行交换，而一般所说的交换是直接将两个字符进行对调，所以计算交换次数的时候不能只算一次。