自动搬运

查看原文

来自洛谷，原作者为

	David_yang 没有一根棒棒糖解决不了的事情，如果有，就再来一根

搬运于2025-08-24 22:46:47，当前版本为作者最后更新于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 过，请放心食用。

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