首页 > 代码库 > 蓝桥杯_基础训练_完美的代价(贪心)

蓝桥杯_基础训练_完美的代价(贪心)

 

基础练习 完美的代价  
 
时间限制:1.0s   内存限制:512.0MB
 
问题描述
  回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
  交换的定义是:交换两个相邻的字符
  例如mamad
  第一次交换 ad : mamda
  第二次交换 md : madma
  第三次交换 ma : madam (回文!完美!)
输入格式
  第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)
  第二行是一个字符串,长度为N.只包含小写字母
输出格式
  如果可能,输出最少的交换次数。
  否则输出Impossible
样例输入
5
mamad
样例输出
3
 
题解:
用贪心,从左往右遍历字符串,对于当前字符,从右往左找相同的。
 
如果找到则把它移动到相应对称位置,
找不到的话如果n为奇数,不能构成回文,如果不是第一个不能匹配的也不能构成回文。
 
 
代码:
#include <iostream>
#include <cstring>
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<j;k++)    //把它移动到对称位置。可以理解为把它后面的字符挨个往前移动一位。然后把结尾下标j--。效果相同
                        a[k]=a[k+1];
                    sum+=j-t;       //计算步数
                    j--;            //结尾下标往前移动一位
                    break;
                }
            }
            if(!ok) break;
        }
        if(!ok) cout<<"Impossible"<<endl;
        else cout<<sum<<endl;
    }
    return 0;
}

 

蓝桥杯_基础训练_完美的代价(贪心)