自动搬运

查看原文

来自洛谷，原作者为

	一念之间、、 Have already AFOed.

搬运于2025-08-24 22:06:29，当前版本为作者最后更新于2021-04-06 16:59:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

（我都没有发现交换次数是逆序对！/jk）

这里提供一个不一样的做法，

首先判断-1就直接看有没有超过两个出现次数为奇数的字符

发现数据范围过大，应该是贪心之类的算法，

一个 naive 考虑从最外面向里面一层一层的求交换次数，每次枚举最左边和最右边填什么字符，选择代价最小的一个填上去，求出总的答案即可。

填一个字符的代价就是找到最靠左的把它放到最左边，找到一个最靠右的，把它放到最右边的交换次数和。

发现这个自己手玩以下 hack 不掉，（后面我们慢慢讨论贪心证明的问题）

考虑实现，同一个字符交换后相对顺序不会发生改变，用一个 deque 存下来，每次一定是使用这个字符最左边和最右边的两个字符， pop_back 和 pop_front 即可

若我们删除了两个字符，相当于在原串挖两个空，考虑用树状数组动态维护当前位置实际位置在哪里。

举个例子

时间复杂度是$O(n*26*\log n)$

考虑证明上面的贪心，我们发现如果我们证明当前选择对后面没有影响即可

假设当前选择的是 AA，下一次选择的是 BB

我们分为3种情况：

1.若呈包含关系，比如 ABBA （这时明显 A 优于 B ），我们贪心的选择是更优的

2.若呈相交关系，比如 ABAB （ BABA 同理），这时若先选 A ，则对选 B 的影响是 -1，先选 B 对 A 的影响也是 -1 ,所以我们贪心选不会影响后面选择。

3.若呈不相交关系，比如 AABB （ BBAA 同理）若先选 A ，则对 B 的影响是 -2 ，先选 B 对 A 的影响是 -2 ，贪心不影响后面选择。

贪心会使答案更优，且不影响选择，所以贪心正确。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
	char c;
	int w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	int ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
const int xx=1e6+5;
char s[xx];
deque<int>t[26];
int lb(int x){return x&(-x);}
int sum[xx],n;
void add(int x,int y)
{
	for(;x<=n;x+=lb(x))sum[x]+=y;
}
int ask(int x)
{
	int ans=0;
	for(;x;x-=lb(x))ans+=sum[x];
	return ans;
}
signed main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)t[s[i]-'A'].push_back(i);
	int tot=0;
	for(int i=0;i<26;i++)if(t[i].size()&1)tot++;
	if(tot>1)return puts("-1"),0;
	ll ans=0;
	for(int i=1;i<=n/2;i++)
	{
		int res=2147483647;
		int now=0;
		for(int j=0;j<26;j++)
		{
			if(t[j].size()<2)continue;
			int l=t[j][0]-ask(t[j][0])-1;//求距离前面还有多远 
			int r=(n-(i-1)*2)-(t[j][t[j].size()-1]-ask(t[j][t[j].size()-1]));//求距离后面还有多远 
			if(l+r<res)res=l+r,now=j;
		}
		ans+=res;
		add(t[now][0],1);//在树状数组里面挖空 
		add(t[now][t[now].size()-1],1);
		t[now].pop_front();
		t[now].pop_back();
	}
	cout<<ans<<"\n";
	return 0;
}