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
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		
		string s;
		cin >> s;
		
		int ost = -1;
		int ile = 0;
		int spacja = 0;
		int spacja_sum = 0;
		int maxim = 0;
		
		priority_queue <pair <int, pair <int, int> > > q; //prior, czy cos odjac, ile
		for(int i = 0; i < n; i++){
			if(s[i] == '1'){
				//cout << "odleglosc " << i - ost - 1 << " miedzy " << ost << " a " << i << "\n";
				if(ile == 0 && i - ost - 1 != 0){
					q.push(make_pair(2 * (i - ost - 1), make_pair(0, (i - ost - 1))));
					//cout << "odleglosc " << i - ost - 1 << " miedzy " << ost << " a " << i << " a\n";
					spacja++;
					spacja_sum += i - ost - 1;
					maxim = max(maxim, i - ost - 1);
				}
				else if(i - ost - 1 != 0){
					q.push(make_pair((i - ost - 1), make_pair(-1, (i - ost - 1))));
					//cout << "odleglosc " << i - ost - 1 << " miedzy " << ost << " a " << i << " b\n";
					spacja++;
					spacja_sum += i - ost - 1;
					maxim = max(maxim, i - ost - 1);
				}
				ile++;
				ost = i;
			}
		}
		
		if(ile == 0){
			cout << "0\n";
			continue;
		}
		
		if(ost != n - 1) {
			q.push(make_pair(2 * (n - ost - 1), make_pair(0, (n - ost - 1))));
			//cout << "odleglosc " << n - ost - 1 << " miedzy " << ost << " a " << n << "\n";
			spacja++;
			spacja_sum += n - ost - 1;
			maxim = max(maxim, n - ost - 1);
		}
		
		//cout << ile << " " << spacja << " " << spacja_sum << " " << maxim << " " << ost << "\n";
		
		int time = 0;
		while(!q.empty()){
			int x = q.top().second.second;
			int odw = q.top().second.first;
			q.pop();
			
			//cout << "usuwam " << x << " z odw= " << odw << ", ";
			
			if(0 <= odw){
				//cout << "dodaje " << min(x, time - odw) << "\n";
				ile += min(x, time - odw);
				if(time - odw < x) time++;
				continue;
			}
			
			if(x <= 2 * time){
				//cout << "dodaje " << x << "\n";
				ile += x;
				continue;
			}
			
			ile += 2 * time;
			//cout << "dodaje " << 2 * time << "\n";
			if(x - 2 * time > 1){
				ile++;
				time++;
				//q.push(make_pair(2 * (x - 2 * time - 1), make_pair(time, (x - 2 * time - 1))));
			}
				
				
			time++;
		}
		
		cout << ile << "\n";
			
	}
}