【31.58%】【codeforces 719B】 Anatoly and Cockroaches

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.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — 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.

Examples

input
5
rbbrr

output
1

input
5
bbbbb

output
2

input
3
rbr

output
0

Note

In the first sample, Anatoly has to swap third and fourth cockroaches. He needs 1 turn to do this.

In the second sample, the optimum answer is to paint the second and the fourth cockroaches red. This requires 2 turns.

In the third sample, the colors of cockroaches in the line are alternating already, thus the answer is 0.

【题解】

这不是道广搜题0 0

可以很容易想到目标序列有两种

1和0分别代表两种不同颜色；

1.以1开头

2.以0开头

构造出这样的目标序列。

然后把所给的初始序列和目标序列对比。

一出现某个位置x不一样就先尝试把

初始序列的x位置上的东西换成目标序列的颜色colorx。

但是换的条件是。换之后。要确定colorx是小于等于目标序列的colorx的颜色个数。

否则就不换.

最后我们可以保证改变之后的序列的两种颜色的数目和目标序列的两种颜色的数目是一样的。

然后如果再有不同就进行交换操作(肯定比单个改变优);

110

101

可以以这个例子看到。进行一次交换必有两个位置都配对了。

可以想象。最后两种颜色都与目标序列的两种颜色数目相同了。

则肯定交换swap操作所需要的数目更少。

就是这样吧。

自己看代码；

【代码】

#include <cstdio>
#include <algorithm>
#include <bitset>

using namespace std;

const int MAXN = 109000;

char s[MAXN];
int len;
long long final_ans = -1;
bitset <MAXN> a, temp, b;

void input_data()
{
	scanf("%d", &len);
	scanf("%s", s);
	for (int i = 1; i <= len; i++)
		if (s[i - 1] == 'b')
			a[i] = 0;
		else
			a[i] = 1;
}

void get_ans(bool chushi)
{
	long long temp_ans = 0;
	temp = a;
	b[1] = chushi;
	for (int i = 2; i <= len; i++)
		b[i] = !b[i - 1];
	int c1[2], c2[2], tc1[2];
	c1[1] = temp.count();
	c2[1] = b.count();
	c1[0] = len - c1[1];
	c2[0] = len - c2[1];
	for (int i = 1; i <= len; i++)
		if (temp[i] != b[i])
		{
			for (int i = 0; i <= 1; i++)
				tc1[i] = c1[i];
			int pre = abs(tc1[0] - tc1[1]);
			tc1[b[i]]++;
			tc1[!b[i]]--;
			if (tc1[b[i]] <= c2[b[i]])//如果改变之后这种颜色的数目小于等于目标序列这种颜色数目
			{//则这个改变是最优的。
				temp[i] = b[i];
				for (int i = 0; i <= 1; i++)
					c1[i] = tc1[i];
				temp_ans++;
			}
		}
	int t2 = 0;
	for (int i = 1; i <= len; i++)//如果还存在不同的。就进行交换操作。
		if (temp[i] != b[i])
			t2++;
	t2 /= 2;//交换可以修正两个不同的位置不匹配;
	temp_ans += t2;
	if (final_ans == -1)
		final_ans = temp_ans;
	else
		final_ans = min(final_ans, temp_ans);
}

void output_ans()
{
	printf("%I64d
", final_ans);
}

int main()
{
	//freopen("F:\rush.txt", "r", stdin);
	input_data();
	get_ans(0);
	get_ans(1);
	output_ans();
	return 0;
}