Codeforces 719B Anatoly and Cockroaches(元素的交叉排列问题)

题目链接：http://codeforces.com/problemset/problem/719/B

题目大意：

　　有一队蟑螂用字符串表示，有黑色 ‘b’ 和红色 'r' 两种颜色，你想使这队蟑螂颜色分布是交叉的，你有两种做法：

　　　　一次调整任意两个交换位置，或者一次给一个蟑螂染色

　　问，最少操作多少次可以使得蟑螂的颜色分布是交叉的。

解题思路：

　　刚看完题，就想到用一个字符接受第一个蟑螂的颜色【下标从0开始】，for 如果是奇数则应该与第一蟑螂的颜色不同，如果相同 ++c1，如果是偶数，就应该与第一个蟑螂的颜色相同，否则++c2。然后找 max(c1,c2)-》c1 要与 c2相匹配的次数+剩余的部分是用燃料涂色的次数，即找到c1 c2中的最大值即可。

　　说了这么多可惜上面的思路只是对了一大半。0.o

　　如果按照上面的思路，操作的次数要取决于第一个字符，如果【修改第一个比按第一个计算存在更少的情况，答案就会出问题】，解决方法：自定义第一元素【存在两种可能 ‘r’ ‘b’ 】，然后按照上面的方法从第一元素比较（下标 0），得到结果,将两种结果找到一较小值即是最终答案。

AC Code:

 1 #include<bits/stdC++.h>
 2 using namespace std;
 3 char ca[100002];
 4 int solve(char c,int n)
 5 {
 6     int c1=0,c2=0;
 7     for(int i=0; i<n; i++)
 8     {
 9         if(c=='r')
10         {
11             if(i&1&&ca[i]!='r')
12                 ++c1;
13             else if((!(i&1))&&ca[i]!='b')
14                 ++c2;
15         }
16         else
17         {
18             if(i&1&&ca[i]!='b')
19                 ++c1;
20             else if((!(i&1))&&ca[i]!='r')
21                 ++c2;
22         }
23     }
24     return max(c1,c2);
25 }
26 int main()
27 {
28     int n;
29     while(scanf("%d",&n)!=EOF)
30     {
31         scanf("%s",ca);
32         cout<<min(solve('r',n),solve('b',n))<<endl;
33     }
34     return 0;
35 }