P9251 tj

David_yang · 2024-08-23 11:00:36 · 题解

传送门

第十篇题解，如有不妥请忽视指出。

题目大意：

给你一个只包含 a 和 b 的字符串，每次操作能交换相邻两个字母的位置。问最少经过几次操作能使字符串变成回文串？无解输出 -1。

算法或数据结构：

只需想一想就可以了。

解析：

在讲之前先强调一下，注意是相邻字母！！！我就是这样被卡了很久……

首先判断无解。很容易想到，当字符串总长度为偶数且 a 的个数（或 b 的个数）为奇数时无解。这部分比较简单，直接特判就行了。

然后就是正常情况。可以发现，我们现在只需要看 a（或 b）就行了，因为其中一种字母对称另一种字母也就对称了。我现在以 a 为例。

在输入的时候，我们就把每个 a 的位置记录下来。判断了无解之后计算每个 a 应该移动几次，加起来。最后在输出前，再判断一下 a 的个数是否为奇数，如果是，那么就把最中间的 a 移到整个字符串的最中间，再算一下要以多少次就行了。

我讲得有点抽象，那就看一下我的代码。再提醒一句：不开 long long 见祖宗！

Code:

#include<bits/stdc++.h>
using namespace std;
long long sum,a[200005],t;
string s;
int main()
{
    cin>>s;
    int len=s.length();
    for(int i=0;i<len;i++)
    {
        if(s[i]=='a')                   //记录每个a的位置
        {
            a[t]=i;
            t++;
        }
    }
    if(!(len&1) && t&1)                 //判断无解
    {
        printf("-1");
        return 0;
    }
    for(int i=0;i<(t>>1);i++)
    {
        sum+=abs(len-1-a[i]-a[t-i-1]);  //计算每个a应该移动多少次，注意要取绝对值
    }
    if(t&1)
    {
        sum+=abs((len>>1)-a[t>>1]);     //如果有落单的，那么把这个a移到整个字符串的最中间
    }
    printf("%lld",sum);
    return 0;
}

注：代码已 AC 过，请放心食用。

最后，浏览过看过也要赞过！