基础训练：完美的代价（回文串）

问题描述

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

输入格式

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

输出格式

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

解题思路

1.首先要考虑的是不能变成完美回文串的情况：当字符串中，字符的个数是奇数的超过1个时，不能变成完美回文串。比如：字符串addbbccc，a有1个，b有2个，c有3个，d有2个。其中，a和c的个数是奇数，所以不能变成完美回文串。
2.搜索的过程要从两边往中间搜索。碰到单个字符没有匹配的对象的情况，先放着，等最后移动到中间。

程序清单

方法一：

#include<iostream>
using namespace std;

int main()
{ int n, flag=0, swap_cnt=0; cin>>n; string str; cin>>str; for(int i=0; i<n-1; i++)
	{ for(int j=n-1; j>=i; j--) //从右往左进行匹配
		{ if(j==i)  //没有匹配的字母 { if(flag==1||str.size()%2==0) { cout<<"Impossible"<<endl; return 0; } flag=1; swap_cnt+=str.size()/2-i; //计算单个字母的交换次数 } else if(str[i]==str[j])  //匹配到位置时 { for(int k=j; k<n-1; k++) { swap(str[k], str[k+1]); //将位置进行交换 swap_cnt++;  //累计交换次数 } n--;  //每搜索完一次后，相应匹配的字母放在最右边。下次搜索从n-1的位置，从右往左匹配。 break; } } } cout<<swap_cnt<<endl; return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
 

方法二：

#include <iostream>
#include <string>
using namespace std;

int main()
{
	int N=0; //N<=8000 
	cin>>N;  //输入字符串的长度
	string str1;
	cin>>str1;
	int a[26]={0};  //统计每个字母出现的次数
	for(int i=0;i<N;i++)
	{
		int index =str1[i]-'a';
		a[index]++; //第i个字母的次数加1 
	}
	int count_odd=0; 
	for(int i=0;i<N;i++)
	{
		if(a[i]%2!=0) count_odd++; //统计字母出现奇数次的个数 
	}
	if(count_odd>=2)
		cout<<"Impossible"<<endl;
	else
	{
		int n=N;
		int swap_count=0;
		for(int i=0; i<(1+N)/2; i++)
		{ int j; for(j=n-1; j>i; j--) //从第n-1个字符向左边搜索  { if(str1[i]==str1[j]) //如果匹配  { while(j<n-1) //进行交换位置  { //char temp; //temp=str1[j+1]; //str1[j+1]=str1[j]; //str1[j]=temp; swap(str1[j],str1[j+1]); j++; swap_count++; // 记录交换次数  } n--;   //对其一组字母后，从右边开始搜索的范围减一  break; //跳出循环，进行下一个位置字母的搜索  } } //当i=j时，说明改字母并没能和其他字母匹配到 if(j==i) { swap_count+=(N-1)/2-i; } }
		cout<<swap_count<<endl;	
	} 
	return 0;
} 

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
 

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/104680436