基础练习 完美的代价

问题描述

　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)

输入格式

　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母

输出格式

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

样例输入

5
mamad

样例输出

3

思路

　　emmm~~~第一眼看到这个题目觉得真的难，后来题目提示了贪心算法才懂，不要去想哪个排在第一个，哪个排在第二个，按题目给的来，举个例子，amdam，第一个字符为a，我就把这个字符当作第一个，然后在从后往前找a，找到了相同之后，相邻两个字符移动，将找到的字符移到第n-1位，然后将尾部减一，便于下次移到第n-2位，如果没找到的话，分为两种情况，
　　1.n%2==0，没找到直接return。
　　2.n%2==1，没找到就计算把这个字符与最中间字符交换所用的次数，这里可能有个疑问了，为什么不直接交换呢？我们假设一个是回文串的字串为ambcbca，当检测到m的时候，count=2，当遍历到它的第四个字符c时，l=3，跳出循环，但此时第四个字符并没有移动，所以前面直接加上的步数就是将第四个字符c与第二个字符将换位置所需要的步数。

AC代码

#include<iostream>
#include<string>
using namespace std;
int main()
{
    int i, j, k, l, n, count = 0, flag = 0;
    string a;
    cin >> n >> a;
    l = n - 1;
    for (i = 0; i < l; i++)
    {
        for (j = l; j >= i; j--)
        {
            if (i == j)
            {
                if (n % 2 == 0 || flag == 1)
                {
                    cout << "Impossible";
                    return 0;
                }
                flag=1;
                count += n / 2 - i;
            }
            else if (a[i] == a[j])
            {
                for (k = j; k < l; k++)
                {
                    swap(a[k], a[k + 1]);
                    count++;
                }
                l--;
                break;
            }
        }
    }
    cout << count;
}

5月24号，重写。AC代码

#include<iostream>
using namespace std;
int flag=0;
int main()
{
    int i,j,n,ans=0;
    string a;
    cin>>n>>a;
    for (i=0;i<n;i++)
    {
        for (j=n-1;j>=i;j--)  //必须要j==i 
        {
            if (i==j) //没找到能和a[i]对称的字符 
            {
                if (a.size()%2==0||flag==1)
                {
                    cout<<"Impossible";
                    return 0;
                }
                flag++;
                ans+=a.size()/2-i;
            }
            else if (a[i]==a[j])  //找到了 
            {
                for (int k=j;k<n-1;k++)
                swap(a[k],a[k+1]);
                ans+=n-1-j;
                n--;
                //此时第一个和最后一个字符对称 
                break;
                //该字符已对称，后面的循环不再考虑最后一个字符 
            }
        }
    }
    cout<<ans; 
}