样例输出20
查看原帖
样例输出20
327069
Lqwq楼主2021/10/13 21:06
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

int s,m[50],dis[50][1000005],sum,ans[1000005];
char a[1000005];
bool v[1000005];
bool check();
void solve1();
void move();

int main()
{
	
	scanf("%s",a+1);
	s=(strlen(a+1));
	
	if(check()==false)
	{
		printf("-1");
		return 0;
	}
	
	if(s%2==1)
	solve1();
	
	move();
	
	return 0;
}

void nxd(int l,int r)
{
	if(l==r)
	return;
	int mid=(l+r)/2;
	nxd(l,mid);
	nxd(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid||j<=r)
	{
		if(i<=mid&&(j>r||ans[i]<ans[j]))
		a[k++]=ans[i++];
		else
		{
			a[k++]=ans[j++];
			sum+=mid-i+1;
		}
	}
	for(int i=l;i<=r;i++)
	ans[i]=a[i];
}

void move()
{
	int i=1,l=1,r=s;
	while(i<=s)
	{
		if(l>r)
		break;
		if(v[i]==false)
		{
			i++;
			continue;
		}
		ans[l]=i;
		l++;
		v[i]=false;
		ans[r]=dis[a[i]-'A'+1][m[a[i]-'A'+1]-1];
		m[a[i]-'A'+1]--;
		v[ans[r]]=false;
		r--;
		i++;
	}
	nxd(1,s);
	printf("%d",sum);
}

void solve1()
{
	int p=0;
	for(int i=1;i<=26;++i)
	{
		if(m[i]%2==1)
		{
			p=dis[i][m[i]/2];
			break;
		}
	}
	ans[s/2+1]=p;
	v[p]=false;
}

bool check()
{
	int num=0;
	bool vis[50];
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=s;i++)
	{
		v[i]=true;
		m[a[i]-'A'+1]++;
		dis[a[i]-'A'+1][m[a[i]-'A'+1]]=i;
	}
	
	for(int i=1;i<=s;i++)
	{
		if(vis[a[i]-'A'+1]==false)
		{
			vis[a[i]-'A'+1]=true;
			if(m[a[i]-'A'+1]%2==1)
			num++;
		}
	}
	
	if((s%2==1&&num>1)||(s%2==0&&num>0))
	return false;
	
	return true;
}
2021/10/13 21:06
加载中...