CF1385D a-Good String(分治)
2021/9/30 23:12:40
本文主要是介绍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(分治)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26解决google chrome helper 内存占用较高!
- 2024-04-01got an unexpected keyword argument
- 2024-03-30维多利亚的秘密 golang入坑系统
- 2024-03-29mongodb sort by date
- 2024-03-29go swagger
- 2024-03-25mongodb cdc
- 2024-03-25how to use go in vscode
- 2024-03-22mongooseserverselectionerror: connect econnrefused ::1:27017
- 2024-03-21pymongo insert_many
- 2024-03-18projection mongodb