蓝桥杯基础练习VIP-完美的代价 （C语言代码）----------------C语言——菜鸟级

解题思路: 用贪心，先保证能构 成回文 由两边向中间查找找 注意边界情况 和特殊情况；
注意事项: 在这代码 可能备注篇幅较大排版有点打脑壳 影响 阅读 可去

 博客查看原文

参考代码:

#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;
}