蓝桥杯练习系统—基础练习 完美的代价

第一部分：题目

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

第二部分：我的思路

1,能否变成回文串：记录每个小写字母的个数，只要奇数的个数不超过1就可以。

2,最少交换次数：贪心：从两端同时开始，不一样的时候需要找到最近的替换：两边的都可以替换，只要交换次数最小也就是最近。

第三部分：代码

#include<iostream>
#include<stdio.h> 
using namespace std;
int main()
{
int len;
    cin>>len;
    getchar();//接收cin的回车符 
char s[8001];
int sum[27]={0};//用来记录26个小写字母的个数 
    gets(s);
for(int i=0;i<len;i++)
    {
        sum[s[i]-'a'+1]++;
    }
int t=0;
//字母个数为奇数的总数超过1就不可能变成回文串。 
for(int i=1;i<27;i++)
    {
if(sum[i]%2!=0)
        {
            t++;
        }
if(t>1)
        {
break;
        }
    }
if(t>1)
    {
        cout<<"Impossible"<<endl;
    }
else
    {
int count=0;
int i,j;
//从两端同时开始，不一样时用离左或右最近的替换：一个一个交换过来。 
for(i=0,j=len-1;i<j;i++,j--)
        {
if(s[i]!=s[j])
            {
int min=10000;
int index;
int flag=0;
//可以替换左边的 
for(int l=i+1;l<j;l++)
                {
if(s[l]==s[j])
                    {
if(min>l-i)
                        {
                            min=l-i;
                            index=l;
break;
                        }
                    }
                }
//可以替换右边的 
for(int l=j-1;l>i;l--)
                {
if(s[l]==s[i])
                    {
if(min>j-l)
                        {
                            min=j-l;
                            index=l;
                            flag=1;
break;
                        }
                    }
                }
                count+=min;
if(flag)
                {
int t=s[index];
for(int k=index;k<j;k++)
                    {
                        s[k]=s[k+1];
                    } 
                    s[j]=t;
                }
else
                {
int t=s[index];
for(int k=index;k>i;k--)
                    {
                        s[k]=s[k-1];
                    } 
                    s[i]=t;
                }
            }
        }
        cout<<count<<endl;
    }
return 0;
}