试题基础练习完美的代价

拼搏现实的明天。 2024-04-01 15:14 81阅读 0赞

## 试题 基础练习 完美的代价 ##

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

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