基础练习 完美的代价  

 

时间限制：1.0s   内存限制：512.0MB

 

问题描述

　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。

　　交换的定义是：交换两个相邻的字符

　　例如mamad

　　第一次交换 ad : mamda

　　第二次交换 md : madma

　　第三次交换 ma : madam (回文！完美！)

输入格式

　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)

　　第二行是一个字符串，长度为N.只包含小写字母

输出格式

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

　　否则输出Impossible

样例输入

5

mamad

样例输出

3

 

题解：

用贪心，从左往右遍历字符串，对于当前字符，从右往左找相同的。

 

如果找到则把它移动到相应对称位置，

找不到的话如果n为奇数，不能构成回文，如果不是第一个不能匹配的也不能构成回文。

 

 

代码：

#include 
       
        #include 
        
         using namespace std;int n;int c;string a;int main(){    while(cin>>n>>a)    {        cnt=0;        c=-1;        int j=n-1;        bool ok=true;        int sum=0;        for(int i=0;i<=j;i++)       //从左往右        {            for(int t=j;t>=i;t--)    //从右往左挨个搜索与a[i]相同的            {                if(i==t)            //如果没有找到                {                    if(n%2==0||c!=-1)   //如果n为偶数，则不能成为回文，或者不是第一个不能匹配的，也不能成为回文                    {                        ok=false;                        break;                    }                                           //到这里的话肯定n是奇数了。                    c=1;               //标记第一个不能匹配的                    sum+=n/2-i;     //为什么不是n/2+1-i呢，因为下标从0开始的，中间的下标是n/2+1-1。                    break;                    //一定要跳出循环，否则有可能会继续执行下面的语句，j--，就错了                }                if(a[t]==a[i])      //如果找到与当前字符相同的                {                    for(int k=t;k