传送门 https://www.luogu.com.cn/problem/P5041

题目描述
所谓回文串，就是对于给定的字符串，正着读和反着读都一样，比如ABCBA就是一个回文串，ABCAB则不是。我们的目标是对于任意输入的字符串，不断将第i个字符和第i+1个字符交换，使得该串最终变为回文串。求最少交换次数。

输入格式
一个由大写字母字母组成的字符串。

输出格式
若能经过有限次操作能将原串变为回文串，则输出最少操作次数；否则输出-1。

考虑贪心，从左往右算

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream> 
#include <vector>
#define int long long 
using namespace std;

const int maxn=1e6+10;
char ch[maxn];
int a[maxn],ans[maxn],s[maxn],b[maxn],vis[maxn],viss[maxn],len,cal;
vector<int>q[30];
int sum;
inline void init(){
   
	scanf("%s",ch+1);
	len=strlen(ch+1);
	cal=0;	
	for(int i=1;i<=len;i++){
   
		a[i]=(int)(ch[i]-'A')+1;
		s[a[i]]++;
		q[a[i]].push_back(i);
	}
	for(int i=1;i<=len;i++){
   
		int zhn=(int)(ch[i]-'A')+1;
		if(!vis[zhn]){
   
			vis[zhn]=1;
			if(s[zhn]&1)cal++; 
		}
	}
	return ;
}
void solve(int l,int r){
   //逆序对 
	if(l==r)return ;
	int mid=(l+r)>>1;
    solve(l,mid);solve(mid+1,r);
    int midd=mid+1,ll=l;
    for(int i=l;i<=r;i++){
   
	  if(midd>r||ll<=mid&&ans[ll]<ans[midd]) b[i]=ans[ll++];
	  else sum+=mid-ll+1,b[i]=ans[midd++];
	} 
	for(int i=l;i<=r;i++) ans[i]=b[i];
}
main(){
   
	
	init();
	
	if(cal>=2) printf("-1");
	else if(len%2==0&&cal) printf("-1");
	else{
   
		if(len&1){
   
			for(int i=1;i<=26;i++){
   
				if(q[i].size()&1){
   
					int lgr=q[i][q[i].size()/2];
					ans[len/2+1]=lgr;
					viss[lgr]=1;
				}
			}	
		}
		int l=1,r=len;
		int pp=1;
		while(pp<=len){
   
			if(viss[pp]){
   
				pp++;
				continue;
			}
			if(pp>len||l>r) break;
			ans[l]=pp;
			viss[pp]=1;
			l++;
			pp++;
			int lgr=q[a[pp-1]][q[a[pp-1]].size()-1];
			ans[r]=lgr;
			viss[lgr]=1;
			r--;
			q[a[pp-1]].erase(q[a[pp-1]].end()-1);
		}
	solve(1,len);
	printf("%lld",sum);
	}
	return 0;
}