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

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;

		string s;
		cin >> s;

		int a, b, first_one, last_one;
		for(a = 0; a<n; ++a){
			if(s[a] == '1') break;
		}
		first_one = a;

		for(b = n-1; b>=a; --b){
			if(s[b] == '1') break;
		}
		last_one = b;

		priority_queue <int> pq;	
		pq.push(0);

		int cnt = 0;
		for(int i = a+1; i<=b; ++i){
			if(s[i] == '0') cnt++;
			else if(cnt != 0){
				pq.push(cnt);
				cnt = 0;
			}
		}

		int begin = first_one;
		int end = n-1-last_one;

		bool one;
		long long ans = 0;
		int days = 0;

		if(begin == n){
			cout << 0 << "\n";
			continue;
		}

		while(begin-days >= 1 || end-days >= 1 || pq.top()-2*days >= 1){
			int maks = pq.top() - 2*days;
			if(maks != 1){
				--maks;
				one = false;
			}else{
				one = true;
			}

			if((maks > begin-days+1 && maks > end-days+1) || (begin-days<=0 && end-days<=0)){
				if(one){
					ans += maks;
				}else{
					ans += maks;
					days++;
				}
				pq.pop();
			}else if(begin >= end){
				ans += begin-days;
				begin = 0;
			}else if(end > begin){
				ans += end-days;
				end = 0;
			}

			++days;
		}

		cout << n-ans << "\n";

	}
	
}