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
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;


void parse(vector<int> &opened_space, vector<int> &closed_space, string &cities) {
    int healthy = 0;
    bool virus_spotted = false;
    for(auto& c: cities) {
        if(c == '1') {
            if(healthy > 0) {
                if(virus_spotted) {
                    closed_space.push_back(healthy);
                }
                else {
                    opened_space.push_back(healthy);
                }
            }
            virus_spotted = true;
            healthy = 0;
        }
        else if(c == '0') {
            ++healthy;
        }
    }
    if(healthy > 0) {
        opened_space.push_back(healthy);
    }
}

int solve(int n, string &cities) {
    vector<int> closed_space, open_space;
    parse(open_space, closed_space, cities);

    make_heap(closed_space.begin(), closed_space.end());
    make_heap(open_space.begin(), open_space.end());

    int t = 0, saved = 0;
    for(t = 0; ; ++t) {
        int open_space_top = -1, closed_space_top = -1;
        if(!open_space.empty()) {
            open_space_top = open_space.front();
        }
        if(!closed_space.empty()) {
            closed_space_top = closed_space.front();
        }
        int open_space_gain = open_space_top - t, open_space_potential = open_space_gain;
        int closed_space_potential = closed_space_top - 2 * t - 1;
        if(open_space.size() >= 2) {
            int tmp = open_space[1] - t - 1;
            if(tmp > 0) {
                open_space_potential += tmp;
            }
        }
        if(open_space_gain < 0 && closed_space_potential < 0) { 
            break;
        }
        if(closed_space_potential > open_space_potential) { 
            ++saved;
            pop_heap(closed_space.begin(), closed_space.end());
            closed_space.pop_back();
            open_space.push_back(closed_space_potential + t);
            push_heap(open_space.begin(), open_space.end());
        }
        else if(open_space_gain <= 0 && closed_space_potential == 0) {
            ++saved;
        }
        else {
            saved += open_space_gain;
            pop_heap(open_space.begin(), open_space.end());
            open_space.pop_back();
        }
    }
    return n - saved;
}

int main() {
    std::ios::sync_with_stdio(false);
    int t, n;
    cin >> t;
    string input;
    for(int i = 0; i < t; ++i) {
        cin >> n >> input;
        cout << solve(n, input) << endl;
    }
}