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
#include<bits/stdc++.h>
using namespace std;
char tab[100010];
priority_queue<pair<int, int>> kolejka;
int main()
{
	int t;
	scanf("%d", &t);
	while(t>0)
	{
		t--;
		int n, i, k=0, w=0;
		scanf("%d", &n);
		scanf("%s", tab+1);
		while(!kolejka.empty())
			kolejka.pop();

		for(i=1;i<=n;i++)
		{
			if(tab[i]=='0')
				k++;
			else
			{
				w++;
				if(k==0)
					continue;
				if(k==i-1)
					kolejka.push({2*k, 0});
				else
					kolejka.push({k, -1});
				k=0;
			}
		}
		if(tab[n]=='0')
		{
			if(k==n)
			{
				printf("0\n");
				continue;
			}
			kolejka.push({2*k, 0});
		}
		int c=0;
		//bool czy=0;
		while(!kolejka.empty())
		{
			int x=kolejka.top().first, y=kolejka.top().second;
			//printf("%d %d-%d ", w, x, y);
			
			if(y==-1)
			{
				if(x<=c*2)
				{
					w+=x;
					kolejka.pop();
					//c++;
					//if(czy==0)
					//	printf("%d %d: ", c, x);
					//czy=1;
					continue;
					//break;
				}
				//printf("%d, ",c);
				//if(czy==1)
				//	printf("NIEE");

				w+=c*2;
				kolejka.pop();
				if(x-2*c-1>0)
					kolejka.push({2*(x+c-1),c});
			}
			else
			{
				int z = x/2-y;
				if(x<=c*2)
				{
					
					w+=z;
					kolejka.pop();
					//c++;
					//czy=1;
					continue;
					//break;
				}
				//if(czy==1)
				//	printf("NIEEEEEEE-%d %d x%dx ", c, x, y);
				w+=c-y;
				//printf("%d_%d , ",c, y);
				kolejka.pop();
			}
			c++;
		}
		printf("%d\n", w);

	}
}