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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;



int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int testy, ilosc, przedzial, znacznik;
    string ciag;

    cin>>testy;

    for(int q=0; q<testy; ++q){

        priority_queue< int > kolejka;
        priority_queue< int > konce;

        cin>>ilosc;
        cin>>ciag;

        przedzial = 0;
        znacznik = 0;

        if( ciag[0] == '0' ){
            znacznik++;
        }

        for( int i=0; i<ciag.length(); ++i){

            if( ciag[i] == '0'){
                przedzial++;
            }

            if( ciag[i] == '1' && przedzial > 0){
                if( znacznik > 0 ){
                    konce.push( przedzial );
                }
                else{
                    kolejka.push( przedzial );
                }
                przedzial=0;
                znacznik=0;
            }

            if( i == ciag.length()-1 ){
                if( ciag[i] == '0' ){
                    znacznik++;
                    konce.push( przedzial );
                }
            }
        }

        int dzien = 0 ;
        int wynik = ilosc;
        int temp = 0 ;

        while( !kolejka.empty())
        {

          //  cout<< kolejka.top().first << " " << kolejka.top().second << endl;

            przedzial = kolejka.top();

            if( !konce.empty()  ) {
                if (konce.top() - dzien > kolejka.top() - 1 - (dzien*2) ){
                    przedzial = max( 0, konce.top() - dzien );
                    dzien++;
                    konce.pop();
                }
                else{
                    przedzial = max(0, kolejka.top() - (dzien*2) );
                    if( przedzial > 1 ){
                        przedzial--;
                        dzien+=2;
                    }
                    if( przedzial == 1 ){
                        dzien++;
                    }
                    kolejka.pop();
                }
            }
            else{
                przedzial = max(0, kolejka.top()  - (dzien*2) );
                if( przedzial > 1 ){
                    przedzial--;
                    dzien+=2;
                }
                if( przedzial == 1 ){
                    dzien++;
                }
                kolejka.pop();
            }

            if( przedzial == 0 ){
                break;
            }

            wynik -= przedzial;

        }

        while( !konce.empty())
        {

            //  cout<< kolejka.top().first << " " << kolejka.top().second << endl;

            przedzial = konce.top();

            if( !kolejka.empty()  ) {
                if (konce.top() - dzien >= kolejka.top() - 1 - (dzien*2) ){
                    przedzial = max( 0, konce.top() - dzien );
                    dzien++;
                    konce.pop();
                }
                else{
                    przedzial = max(0, kolejka.top()  - (dzien*2) );
                    if( przedzial > 1 ){
                        przedzial--;
                        dzien+=2;
                    }
                    if( przedzial == 1 ){
                        dzien++;
                    }
                    kolejka.pop();
                }
            }
            else{
                przedzial = max(0, konce.top() - dzien );
                dzien+=1;
                konce.pop();
            }

            if( przedzial == 0 ){
                break;
            }

            wynik -= przedzial;

        }

        cout << wynik << endl;
    }

}