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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <stdlib.h>

int t, n, it;
char input[100002];

typedef struct {
	int cnt;
	int d;
} group_t;

int compar(const void *pa, const void *pb)
{
	const group_t *ga = (const group_t *) pa;
	const group_t *gb = (const group_t *) pb;
	int a = 2 * ga->cnt / ga->d;
	int b = 2 * gb->cnt / gb->d;
	int r = b - a;
	return r;
}

group_t group[100001];
int groups;

#ifdef	DEBUG
#define	DBG(x)	(x)
static void dump(void)
{
	int i;

	fprintf(stderr, "t=%d, groups(%d):", it, groups);
	for (i = 0; i < groups; i++) {
		fprintf(stderr, " %d(%d)", group[i].cnt, group[i].d);
	}
	putc('\n', stderr);
}
#else
#define	dump()
#define	DBG(x)
#endif

static void pan(void)
{
	int i, days, saved;
	group_t *g = NULL;

	scanf("%d\n", &n);
	fgets(input, sizeof(input), stdin);
	groups = 0;
	for (i = 0; i < n; i++) {
		int z = input[i] == '0';

		if (z) {
			if (!g) {
				g = &group[groups];
				g->cnt = 0;
				g->d = !!i;
				groups++;
			}
			g->cnt++;
		} else {
			if (g) {
				g->d++;
				if (g->d > g->cnt)
					g->d = g->cnt;
				g = NULL;
			}
		}
	}
	qsort(group, groups, sizeof(group_t), compar);
	dump();

	days = saved = 0;
	for (i = 0, g = group; i < groups; i++, g++) {
		int d = g->d;
		int cnt = g->cnt - days * d;
		if (cnt < 0)
			cnt = 0;

		if (d > cnt)
			d = cnt;

		int s = cnt - (d ? d - 1 : 0);
		DBG(fprintf(stderr, "i=%d, cnt=%d, d=%d, s=%d\n", i, cnt, d, s));
		saved += s;
		days += d;
	}

	printf("%d\n", n - saved);
}

int main(void)
{
	scanf("%d\n", &t);
	for (it = 0; it < t; it++)
		pan();

	return 0;
}