CF1385D a-Good String（分治）

本文主要是介绍CF1385D a-Good String（分治），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一种分治的思想，看每次的左右区间，找一个需要更改小的进行更改，然后对另一个区间进行继续往下分治的更改。

#include<cstdio>
#include<iostream>
using namespace std;
int T,n;
char s[200005];
int solve(int l,int r,char c){
	if(l==r){
		if(s[l]==c) return 0;
		return 1;
	}
	int cnt=0,tot=0;
	int mid=(l+r)>>1;
	for(int i=l;i<=mid;i++){
		if(s[i]!=c) cnt++;
	}
	for(int i=mid+1;i<=r;i++){
		if(s[i]!=c) tot++;
	}
	cnt+=solve(mid+1,r,(char)(c+1));
	tot+=solve(l,mid,(char)(c+1));
	return min(cnt,tot);
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		scanf("%s",s+1);
		printf("%d\n",solve(1,n,'a'));
	}
	return 0;
}

这篇关于CF1385D a-Good String（分治）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！