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

inline int second_largest(priority_queue<int>& q)
{
    int tmp = q.top();
    q.pop();
    int res = q.top();
    q.push(tmp);
    return res;
}

int solve(const vector<int> &_inner, const vector<int> &_outer)
{
    priority_queue<int> inner(_inner.begin(), _inner.end()), outer(_outer.begin(), _outer.end());
    int inner_delta = 0, outer_delta = 0;
    int res = 0;

    while ((!inner.empty() && inner.top() + inner_delta > 0)
        || (!outer.empty() && outer.top() + outer_delta > 0)) {
        int inner_val = inner.empty() ? -1 : inner.top() + inner_delta;
        int outer_val = outer.empty() ? -1 : outer.top() + outer_delta;
        int outer_val2 = outer.size() < 2 ? -1 : second_largest(outer) + outer_delta;

        if (outer_val > 0 && ((outer_val2 > 0 && outer_val + outer_val2 - 1 >= inner_val - 1)
            || (outer_val2 <= 0 && outer_val >= inner_val - 1))) {
            // take outer
            res += outer_val;
            outer.pop();
        }
        else {
            // take inner
            res += 1; // 1 vaccinated, so saved
            inner.pop();
            outer.push(inner_val - 1 - outer_delta);
        }

        inner_delta -= 2;
        outer_delta -= 1;
    }

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;

    int test_case = 0;
    for (; t > 0; t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        // healthy: inner and outer
        vector<int> inner;
        vector<int> outer;
        int last_length = 1;
        int last_kind = s[0];
        bool first = true;
        for (int i = 1; i < n; i++) {
            if (s[i] == s[i - 1]) {
                last_length++;
            }
            else {
                if (last_kind == '0') {
                    if (first) {
                        outer.push_back(last_length);
                    }
                    else {
                        inner.push_back(last_length);
                    }
                }
                last_kind = s[i];
                last_length = 1;
                first = false;
            }
        }

        if (last_kind == '0') {
            outer.push_back(last_length);
        }

        cout << (n - solve(inner, outer)) << "\n";
    }
}