可以将相同的人数分块存在数组gp中先
例如RRGGGRBBBBRR
则gp[1~5]={2,3,1,4,2}
首先可以知道,如果要让没有相邻的相同,只需要每个gp[i]/2向下取整即可得出最少需要改变的个数
例如RGGGR,只看G,只需要改变中间的G即可
例如RGGGGR,只看G,可以选择改变1和3或者2和4位置的G、
最后,考虑首尾成环对答案的影响
例如RRRGRRR
gp[1~3]={3,1,3}
则由上面的说法可以得到答案为3/2+1/2+3/2=1+0+1=2人
但实际上首尾连接后有6个R坐在一起
至少需要改变3个人才能满足题意
另,如果所有人都同色
例如RRRRR
根据上面说法只需要改变5/2=2人
即改变2和4位置的人
但是这样1和5首尾相连后会导致同色的人坐在一起
这种情况下答案需要特判为(5+1)/2=3人
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
ios::sync_with_stdio();cin.tie();
int T,t,N,m,i,gp[],ans;
string s;
cin>>T;
for(t=;t<=T;t++){
cin>>N>>s;
s=" "+s;//下标移位
ans=m=;
for(i=;i<=N;i++)
if(s[i]==s[i-])
gp[m]++;
else
gp[++m]=;
if(s[]==s[N]&&N!=)
if(m!=){
gp[]+=gp[m];
m--;
}
else
gp[]++;
for(i=;i<=m;i++)
ans+=gp[i]/;
cout<<"Case #"<<t<<":\n"<<ans<<'\n';
} return ;
}