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

0
14

问题描述
  回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
  交换的定义是:交换两个相邻的字符
  例如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 }

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

<

发布回复

请输入评论!
请输入你的名字