Submission #70199225

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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 {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#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