可以将相同的人数分块存在数组 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 人
- /*
- Written By StelaYuri
- */
- #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<<":\n"<<ans<<'\n';
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3395564.html