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

int main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int t;
    int n;
    bool test;
    int licznik = 0;
    int suma = 0;
    int dl = 0;
    string s;
    int lewy, srodek, prawy;
    cin >> t;
    for (int k = 0; k < t; k++) {
        test = true;
        suma = 0;
        licznik = 0;
        priority_queue<int> q;
        cin >> n;
        cin >> s;
        if (s[0] == '0') {
            dl = 1;
        } else {
            dl = 0;
            lewy = 0;
            test = false;
        }
        for (int i = 1; i < n; i++) {
            if (s[i] == '0') {
                dl++;
            } else {
                if (test) {
                    lewy = dl;
                } else if (dl != 0) {
                    q.push(dl);
                }
                dl = 0;
                test = false;
            }
        }
        if (s[s.size()-1] == '0') {
            prawy = dl;
        }
        while (!q.empty()) {
            if (lewy - licznik > 0) {
                if (lewy - licznik >= q.top() - licznik * 2) {
                    suma += lewy-licznik;
                    licznik++;
                    lewy = 0;
                    continue;
                } else if (prawy - licznik > 0) {
                    if (prawy - licznik > q.top() - licznik * 2) {
                        suma += prawy-licznik;
                        licznik++;
                        prawy = 0;
                        continue;
                    }
                }
            } else if (prawy - licznik > 0) {
                if (prawy - licznik > q.top() - licznik * 2) {
                    suma+= prawy - licznik;
                    licznik++;
                    prawy = 0;
                    continue;
                }
            }
            if (q.top() - licznik * 2 - 1 > 0) {
                suma += q.top() - licznik * 2 - 1;
                licznik+=2;
            }
            q.pop();
        }
        if (lewy - licznik > 0) {
            suma += lewy - licznik;
            licznik++;
        }
        if (prawy - licznik > 0) {
            suma += prawy - licznik;
        }
        cout << n-suma << '\n';

    }



}