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
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);

        int t;
        std::cin >> t;
        while (t--) {
                int n;
                std::cin >> n;
                std::string s;
                std::cin >> s;

                int edge1 = -1, edge2 = -1;
                int curr = 0;
                std::vector<int> v;

                for (int i = 0; i < n; i++) {
					if (s[i] == '0') curr++;
					else {
						if (edge1 == -1) edge1 = curr;
						else v.push_back(curr);
						curr = 0;
					}
                }

                if (edge1 == -1) edge1 = 0;
                if (edge2 == -1) edge2 = 0;
                edge2 = curr;
                if (edge1 < edge2) std::swap(edge1, edge2);
                std::sort(v.begin(), v.end(), std::greater());

                int days = 0;
                int vac = 0;

                for (int i = 0; i < v.size(); i++) {
                        int y = v[i] - 2*days;
                        if (y > 1) y--;
						if (y == 4 && edge1-days > 0 && edge2-days-1 > 0) {
							if (i == v.size()-1 || edge1+edge2 > v[i+1]) {
								i--;
								vac += edge1-days;
								vac += edge2-days-1;
								days++;
								edge2 = 0;
								days++;
								edge1 = edge2;
								edge2 = 0;
								continue;
							}
						} else if (y == 2) {
							if (edge1-days > 0) {
								i--;
								vac += edge1-days;	
								days++;
								edge1 = edge2;
								edge2 = 0;
								continue;
							}
						}
                        if (y > edge1-days) {
                                if (y <= 0) continue;
                                vac += y;
                                days += 2;
                        } else {
                                if (edge1-days <= 0) continue;
                                vac += edge1-days;
                                days++;
                                i--;
                                edge1 = edge2;
                                edge2 = 0;
                        }
                }

				if (edge1-days > 0) vac += edge1-days;
				if (edge2-days-1 > 0) vac += edge2-days-1;

                std::cout << n - vac << '\n';
        }

        return 0;
}