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();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 ;

}

巴特西

ZJNU 1531 - 丢手绢--中级

最新文章

热门文章