Anatoly and Cockroaches
time limit per test 1 second memory limit per test 256 megabytes
input standard input output standard output

Anatoly lives in the university dorm as many other students do. As you know, cockroaches are also living there together with students. Cockroaches might be of two colors: black and red. There are n cockroaches living in Anatoly’s room.
Anatoly just made all his cockroaches to form a single line. As he is a perfectionist, he would like the colors of cockroaches in the line toalternate. He has a can of black paint and a can of red paint. In one turn he can either swap any two cockroaches, or take any single cockroach and change it’s color.
Help Anatoly find out the minimum number of turns he needs to make the colors of cockroaches in the line alternate.

传送门:CF719B

Input

The first line of the input contains a single integer n (1≤n≤100000) — the number of cockroaches. The second line contains a string of length n, consisting of characters 'b' and 'r' that denote black cockroach and red cockroach respectively.

Output

Print one integer — the minimum number of moves Anatoly has to perform in order to make the colors of cockroaches in the line to alternate.

Sample Input

1
2
5
rbbrr

Sample Output

1
1

题解

哈哈哈博主做题时脑抽了 In one turn he can either swap any two cockroaches, In one turn he can either swap any two cockroaches, In one turn he can either swap any two cockroaches, 请读三遍,这是可以任意交换两个啊,博主做的时候以为只能交换相邻的...然后花式WA... 那么这个问题就很简单了,首先目标状态只有两种: 要么是rbrbrbrbrbrbrbr...... 或者brbrbrbrbrbrbrb...... 所以我们只要分别统计原字符串和这两个字符串有多少处错误, 然后 关键的一点:举个例子 原input:rrbr 一:对照rbrb 那么这里1,3号位错了,b1有两个错, 2号位错了,r1有一个错,所以我们可以交换一次rb,然后把剩下的一个b改成r 所以操作数为2,也就是说这种情况下答案是Math.max(b1,r1)=2。 二:对照brbr 0号位错了,b2有一个错,r2没有错 这种情况下答案是Math.max(b2,r2)=1。 最后两种情况下取最小就行了。
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.io.*;  
import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
String s1=sc.next();
StringBuilder s=new StringBuilder(s1);
int l=s.length();
int count1r=0;
int count1b=0;
//count1:count for mistakes of string which is compared with rbrbrbrbrbrbrbrbrb
int count2r=0;
int count2b=0;
//count2:count for mistakes of string which is compared with brbrbrbrbrbrbrbrbr
for(int i=0;i<l;i++){
if(i%2!=0){
if(s.charAt(i)=='r'){
count1r++;
}
if(s.charAt(i)=='b'){
count2b++;
}
}
else{
if(s.charAt(i)=='r'){
count2r++;
}
if(s.charAt(i)=='b'){
count1b++;
}
}
}

System.out.println(Math.min(Math.max(count1r, count1b),Math.max(count2r, count2b)));
}

}
}