手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

cf 732D. Kill Anton(思维,归并排序求逆序对)

时间:2021/6/9 1:07:12|来源:|点击: 次

传送门
在这里插入图片描述
Example
input
4
ANTON
NAAN
AAAAAA
OAANTTON
output
NNOTA
AANN
AAAAAA
TNNTAOOA
在这里插入图片描述
大致题意:
求a的一种排列b使得b通过相邻字符交换变成a时交换的次数最多,且交换方案均为最优(即字符串从b变为a时字符间的交换次数最少)

思路:(各位大佬的,我是真的没想到)
形成最佳的b一定满足相同的字符是排列在一起的;
举例说明叭:
在这里插入图片描述
可知当A在最右的时候为最优方案;
以此类推,当每种字母都在其他字母的某一侧时可得一种最优方案;
即我们只需查找四种字母连续排列的不同情况(可以通过内置函数next_permutation进行全排列操作由于只有四种字母所以还是可行的)即可得到一种最优b;
对于操作数我们可以通过将字符串转换为一串数字,求数字中的逆序对个数即求交换所需操作数;
求逆序对两种常用方法:1.归并排序2.树状数组
这里用了归并排序,若下次有空可以补补树状数组~

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[50];//记录字符个数 
vector<int>id[50],c;//记录字符 
string s;ll nxt;
void msort(int l,int r){//归并排序 
	if(l>=r)return;//区间元素小于1 
	int mid=l+r>>1;
	msort(l,mid);//分 
	msort(mid+1,r);//分 
	int i=l,j=mid+1,k=0;
	int t[r-l+1];
	while(i<=mid&&j<=r){
		if(c[i]<=c[j])t[k++]=c[i++]; 
		else{//此时存在逆序对,在归并过程中记录逆序对的个数 
			t[k++]=c[j++];
			nxt+=mid-i+1;//记录逆序对数 
		}
	}
	while(i<=mid)t[k++]=c[i++];
	while(j<=r)t[k++]=c[j++];
	for(i=l,k=0;i<=r;i++,k++)c[i]=t[k];//将t排好序的数复制到c中 
} 
int main()
{
    ios_base::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--){
		int r[5]={0,'A','N','O','T'};//通过函数枚举各种可能性; 
		memset(a,0,sizeof(a));//清空 
		id['A'-'A'].clear();
		id['N'-'A'].clear();
		id['O'-'A'].clear();
		id['T'-'A'].clear();
		cin>>s;
		for(int i=0;i<s.size();i++){
			a[s[i]-'A']++;//记录每个字母的个数 
			id[s[i]-'A'].push_back(i+1); 
		}
		ll ans=0;string as;
		do{
			c.clear();
			nxt=0;//清零记录下一种情况的操作数
			for(int i=1;i<=4;i++){//四个字符分别连续存入形成一个新的字符串 
				c.insert(c.end(),id[r[i]-'A'].begin(),id[r[i]-'A'].end());
			}
			msort(0,c.size()-1);
			if(nxt>ans){
				ans=nxt;
				as="";
				for(int i=1;i<=4;i++) as+=string(a[r[i]-'A'],(char)r[i]);//存入此时的最优字符串,即前面c的原串 
			}
		}while(next_permutation(r+1,r+5));//对四个字符全排列的各种可能性; 
		if(ans!=0)cout<<as<<endl;
		else cout<<s<<endl;//ans为0说明原字符串已经为最优解 
	} 
    return 0;
}

Copyright © 2002-2019 某某自媒体运营 版权所有