Submission #70199225

---

Source Code Expand

#include <stdio.h>

int N;
char S[512345];

int main(void) {
	int T, tc;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		int zero_all = 0, zero_cur = 0, zero_max = 0;
		int one_all = 0, one_cur = 0, one_max = 0;
		int i;
		int c1, c2;
		if (scanf("%d", &N) != 1) return 1;
		if (scanf("%512343s", S + 1) != 1) return 1;
		for (i = 1; i <= N; i++) {
			if (S[i] == '1') {
				one_all++;
				if (++one_cur > one_max) one_max = one_cur;
				zero_cur = 0;
			} else {
				zero_all++;
				if (++zero_cur > zero_max) zero_max = zero_cur;
				one_cur = 0;
			}
		}
		c1 = (zero_all - zero_max) * 2 + one_all;
		c2 = (one_all - one_max) * 2 + zero_all;
		printf("%d\n", c1 <= c2 ? c1 : c2);
	}
	return 0;
}

/*

多分一番でかいブロックを活用するのがいい
残すブロック以外で
残すブロックと同じ文字 → 2回反転
残すブロックと違う文字 → 1回反転
いずれも、操作後残すブロックに突っ込めばいい

*/

Submission Info

Judge Result