题目链接http://codeforces.com/problemset/problem/719/B
思路
不论输入什么，最终序列只有两种rbrbrb,brbrbr两种
找输入串和最终序列错位的个数，这些错位数一定要花费一次.
有两种组合，max(r[0],b[1])和max(r[1],b[0]);
max(r[0],b[1])表示rbrbrb这种序列的最大错位数，即花费次数
max(r[1],b[0])表示brbrbr这种序列的最大错位数。
以题目中样例1举例:
5
rbbrr核心代码
rep(i,0,n)
{
if(s[i]=='r')
r[i&1]++;
if(s[i]=='b')
b[i&1]++;
}
int ans=min(max(b[0],r[1]),max(b[1],r[0]));case1:
最终序列rbrbr
输入序列rbbrr
r[0]表示i为偶数(i&1==0)，s[i]==r
b[1]表示i为奇数(i&1==1), s[i]==b
r[0]=1; //输入序列的第四个错位
b[0]=1;//输入序列的第三个错位
max(r[0],b[1])=1;
case2:
最终序列brbrb
输入序列rbbrr
r[1]表示i为奇数(i&1==1)，s[i]==r
b[0]表示i为偶数(i&1==0), s[i]==b
r[0]=2; //输入序列的第四个错位
b[0]=1;//输入序列的第三个错位
max(r[0],b[1])=2;
ans=min( …. , …. )求两种case较小的次数
完整代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i,a,b) for(i=a;i<b;i++)
using namespace std;
char s[100010];
int r[2],b[2];
int main(){
int i,n;
scanf("%d",&n);
scanf("%s",s);
rep(i,0,n)
{
if(s[i]=='r')
r[i&1]++;
if(s[i]=='b')
b[i&1]++;
}
int ans=min(max(b[0],r[1]),max(b[1],r[0]));
printf("%d\n",ans);
return 0;
}