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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//Szymon Januszek 3LO Gdynia
#include <bits/stdc++.h>

using namespace std;

//change at pos, total time
pair<int, int> prefix[100001];

int main() {
    int t;
    cin >> t;

    while(t--) {
        int n;
        scanf(" %d", &n);

        vector<pair<int, bool>> vect;
        vector<int> terminal;
        vect.push_back({0, 0});

        int last_state = '1', range_start = 0, healty_start = 0;
        char c;

        while((c = getchar()) < '0');

        for(int i = 0; i < n; i++) {
            if(c == '0') healty_start++;

            if(c != last_state) {
                if(c == '1') {
                    if(!range_start) terminal.push_back(i);
                    else vect.push_back({i - range_start, 0});
                }

                range_start = i;
            }
            last_state = c;
            c = getchar();
        }

        if(last_state == '0') terminal.push_back(n - range_start);

        if(healty_start == n) {
            printf("0\n");
            continue;
        }

        if(healty_start == 0) {
            printf("%d\n", n);
            continue;
        }

        sort(++vect.begin(), vect.end(), greater<pair<int, bool>>());
        sort(terminal.begin(), terminal.end(), greater<int>());

        pair<int, int> templ = {0, 0};

        fill(&prefix[0], &prefix[vect.size() + 1], templ);

        int ww = 0;

        int m = 0, last_element = 0;

        for(int i = 1; i < vect.size(); i++) {
            int d = vect[i].first - 2*m;

            if(d == 1) {
                ww++;
                m++;
            } else if(d > 1) {
                ww += --d;
                m += 2;
            } else break;

            prefix[i] = {d, m};
            last_element = i;
        }

        for(int x: terminal) {
            //max delta at pos
            pair<int, int> mdp = {0, 0};
            bool update = false;

            for(int i = last_element + 1; i > 0; i--) {
                if(vect[i].second) break;

                if(prefix[i - 1].second < x) {
                    int d = x - prefix[i - 1].second;

                    if(i <= last_element) d -= (last_element - i + 1) * 2;

                    if(i <= last_element && prefix[last_element].first < 3) d++;

                    if(d >= mdp.first) {
                        mdp = {d, i};
                        update = true;
                    }
                }
            }

            if(update) {
                vect.insert(vect.begin() + mdp.second, {x, 1});

                ww = 0;
                m = 0;
                for(int i = 1; i < vect.size(); i++) {
                    int d;
                    if(vect[i].second) {
                        d = vect[i].first - m;

                        if(d > 0) {
                            ww += d;
                            m++;
                        } else break;
                    } else {
                        d = vect[i].first - 2*m;
                        if (d == 1) {
                            ww++;
                            m++;
                        } else if (d > 1) {
                            ww += --d;
                            m += 2;
                        } else break;
                    }

                    prefix[i] = {d, m};
                    last_element = i;
                }
            } else break;
        }

        printf("%d\n", n - ww);
    }

    return 0;
}