蓝桥杯 基础训练 完美的代价--------------C语言—菜鸟级

/*问题描述
　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。
小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，
请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)
输入格式
　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母
输出格式
　　如果可能，输出最少的交换次数。
　　否则输出Impossible
样例输入
5
mamad
样例输出
3
思路： 用贪心，先保证能构 成回文 由两边向中间查找找 注意边界情况 和特殊情况；

*/

#include<stdio.h>
#include <string.h>
int main()
{ 
char a[8005];//存储字符串 
char b[8005];//用于判断字符串能否构成字符串； 
long long i,j,len,t=1,t1=0,sum=0;
scanf("%lld\n",&len);
  for(i=0;i<len;i++)
  {scanf("%c",&a[i]);
     b[i]=a[i];
  }

       for(i=0;i<len-1;i++)
     for(j=i+1;j<len;j++)
       if(b[i]>b[j]){char c=b[i];b[i]=b[j];b[j]=c;}//按ASCII 值排序便于统计 
       
       for(i=0;i<len;i++) 
         if(b[i]==b[i+1]&&i<len){t++;}//统计每个相同字符的数量 
         else                         //用于判断字符串能否构成字符串；
		 { if(t%2==1)t1++;//若字符数量为奇数 且为奇数字符的种类大于等于2则不能构成回文 
		    if(t1>=2)break;
			  t=1; }
         if(t1>=2)printf("Impossible\n");
         else
		 { i=0;//从第一位字符（0位）寻找对应字符；第一位对应最后一位 因此需找到与之匹配的字符换到最后一位 
		    for(j=len-1;j>i;j--)//为次数最小则就近原则 从后向前查找遇到的第一个匹配字符则通过相邻字符交换 
		    { for(t=j;t>i;t--)//到对应位置  从匹配字符位到与查找对应位置根据交换原则，交换后两个交换位置 
		      if(a[t]==a[i])//之间 的字符循序不变 可视为移位插入法（i 对应位置 是j 匹配字符 是t;则从t交换 
		      {sum+=j-t;//到j 则需 j-t 次； 
		      b[0]=a[t];
		      while(t<j)
		      {a[t]=a[t+1];t++;}  //移位 
		        a[j]=b[0];i++;break;//匹配字符插入对应位 然后i++寻找下一位 
			  }
			  if(t==i&&j!=i){j++;char c=a[i];a[i]=a[i+1];a[i+1]=c;sum++;}//若查找的对应字符为中心（奇数）字符 
			                                                            // 且不是查找 中心（奇数）字符 的对应位 
		    }                                                           // 则先将 中心（奇数）字符与非中心字符交换重找此对应位 
			printf("%lld\n",sum);
			
     }
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
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/79766806