ZJNU 1531

可以将相同的人数分块存在数组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(0);cin.tie(0);
    int T,t,N,m,i,gp[110],ans;
    string s;
    cin>>T;
    for(t=1;t<=T;t++){
        cin>>N>>s;
        s=" "+s;//下标移位
        ans=m=0;
        for(i=1;i<=N;i++)
            if(s[i]==s[i-1])
                gp[m]++;
            else
                gp[++m]=1;
        if(s[1]==s[N]&&N!=1)
            if(m!=1){
                gp[1]+=gp[m];
                m--;
            }
            else
                gp[1]++;
        for(i=1;i<=m;i++)
            ans+=gp[i]/2;
        cout<<"Case #"<<t<<":
"<<ans<<'
';
    }
    
    return 0;
}