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

using namespace std;

vector<int> lengths;

int main() {
    int t;
    scanf("%d", &t);
    int n; char c;
    for(int i=0; i<t; ++i) {
        lengths.clear();
        scanf("%d",&n);
        //printf("%d\n",n);
        int length=0;
        c=getchar();
        for(int j=0; j < n; ++j) {
            c=getchar();
            //printf("%c",c);
            if(c=='0') length++;
            else {
                lengths.push_back(length);
                length=0;
            }

        }
        lengths.push_back(length);
        //printf("\n");
        //for(auto c : lengths) printf("%d",c);
        //printf("\n");

        if(lengths.size()==1) {
            printf("%d\n",n-lengths[0]);
            continue;
        }

        sort(lengths.begin()+1,lengths.end()-1);
        reverse(lengths.begin()+1,lengths.end()-1);
        //for(auto c : lengths) printf("%d ",c);
        //printf("\n");
        int time=0;
        int position=1;
        int saved=0;
        int l0=lengths[0];
        int ll=lengths[lengths.size()-1];
        int lm;
        bool mode1=false;
        if(position < lengths.size()-1) {
            lm=lengths[position]-(2*time);
            if(lm > 1) { mode1=false; lm -= 1; }
            else mode1=true;
        }
        else lm=0;

        while(l0 > 0 || ll > 0 || lm > 0) {
            //printf("l0=%d, ll=%d, lm=%d \n",l0,ll,lm);
            if(l0 >= max(ll,lm)) {
                saved+=l0;

                //printf("saved: %d\n",saved);

                l0=0;
                ll--;
                time+=1;

                if(position < lengths.size()-1) {
                    lm=lengths[position]-(2*time);
                    if(lm > 1) { mode1=false; lm -= 1; }
                    else mode1=true;
                }
                else lm=0;

                continue;
            }
            if(ll >= max(l0,lm)) {
                saved+=ll;

                //printf("saved: %d\n",saved);

                ll=0;
                l0--;
                time+=1;

                if(position < lengths.size()-1) {
                    lm=lengths[position]-(2*time);
                    if(lm > 1) { mode1=false; lm -= 1; }
                    else mode1=true;
                }
                else lm=0;


                continue;
            }

            saved+=lm;

            //printf("saved: %d\n",saved);

            if(mode1) {
                time+=1;
                ll--;
                l0--;
            }
            else {
                time+=2;
                l0-=2;
                ll-=2;
            }
            position++;

            if(position < lengths.size()-1) {
                lm=lengths[position]-(2*time);
                if(lm > 1) { mode1=false; lm -= 1; }
                else mode1=true;
            }
            else lm=0;

        }
        printf("%d\n",n-saved);
    }
    return 0;
}