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

using namespace std;

int main() {
    int n, t;
    char c;
    cin >> t;
    for (int ti = 0; ti < t; ++ti) {
        vector<int> sofars;
        int saved = 0;
        int sofar = 0;
        bool special = true;
        int special1, special2;
        int bigspecial, smallspecial;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> c;
            if (c=='1') {
                if (sofar > 0 || special) {
                    if (special) {
                        special1 = sofar;
                        special = false;
                    } else {
                        sofars.push_back(sofar);
                    }
                }
                sofar = 0;
            } else {
                sofar++;
            }
        }
        if (sofar == n) {
            cout << "0" << endl;
            continue;
        }

        special2 = sofar;
        if (special1 >= special2) {
            bigspecial = special1;
            smallspecial = special2;
        } else {
            bigspecial = special2;
            smallspecial = special1;
        }
        if (sofars.empty()) {
            int bigspec_saved = bigspecial;
            int smallspec_saved = max(smallspecial - 1, 0);
            cout << n - bigspec_saved - smallspec_saved << endl;
            continue;
        }

        sort(sofars.begin(), sofars.end(), greater<>());

        int specials[3];
        specials[0] = bigspecial;
        specials[1] = smallspecial;
        specials[2] = 0;
        int specidx = 0;
        int turns = 0;
        int totalsaved = 0;
//        cerr << "SPECIALS: " << specials[0] << " " << specials[1] << " " << specials[2] << endl;
//        cerr << "ALL SEGMENTS: ";
//        for (int i = 0; i < sofars.size(); ++i) {
//            cerr << sofars[i] << " ";
//        }
//        cerr << endl;
        for (int i = 0; i < sofars.size(); ++i) {
            int best_sofar = sofars[i] - (2 * turns);
            int best_special = specials[specidx] - turns;
//            cerr << "CHECKING SOFAR " << i << " OUT OF " << sofars.size() << endl;
//            cerr << "BEST SOFAR:   " << best_sofar << endl;
//            cerr << "BEST SPECIAL: " << best_special << endl;
             if (best_special >= best_sofar - 2 && best_special > 0) {
                // take special
                totalsaved += best_special;
                specidx++;
                turns++;
                i--;
            } else {
                // take biggest segment
                if (best_sofar <= 0) {
                    break;
                } else if (best_sofar == 1 || best_sofar == 2) {
                    totalsaved += 1;
                    turns += 1;
                } else {
                    totalsaved += best_sofar - 1;
                    turns += 2;
                }
            }
        }
        int best_special = specials[specidx] - turns;
        if (best_special > 0) {
            // take special
            totalsaved += best_special;
            specidx++;
            turns++;
        }
        best_special = specials[specidx] - turns;
        if (best_special > 0) {
            // take special
            totalsaved += best_special;
            specidx++;
            turns++;
        }
        cout << n - totalsaved << endl;
    }
    return 0;
}