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

using namespace std;

int main() {
    int T;
    cin>>T;
    for(int t=0; t<T; ++t) {
        int N;
        cin>>N;
        string S;
        cin>>S;
        int L = 0;
        vector<int> V,W;
        for(int i=0; i<=N; ++i) {
            if(i == N || S[i] =='1') {
                if(L > 0) {
                    V.push_back(L);
                    L = 0;
                }
            }
            else if(S[i] == '0') {
                L++;
            }
        }
        if(V.size() == 1 && S[0] == '0' && S[N-1] == '0') {
            cout<<0<<endl;
            continue;
        }
        if(S[0] == '0') {
            W.push_back(V[0]);
            V.erase(V.begin());
        }
        if(S[N-1] == '0') {
            W.push_back(V[V.size()-1]);
            V.erase(V.begin() + V.size() - 1);
        }
        sort(W.begin() , W.end());
        sort(V.begin() , V.end());
        reverse(V.begin(), V.end());
        int Licznik = 0, w = W.size() - 1, i = 0;
        int ans = 0;
        while(true) {
            int M,O;
            if(i < V.size()) M = max(V[i] - Licznik * 2 , 0);
            else M = 0;
            if(w >= 0) O = max(W[w] - Licznik , 0);
            else O = 0;
            if(O == 0 && M == 0) break;
            if(O >= (M+1) / 2) {
                ans += O;
                Licznik++;
                w--;
            }
            else {
                if(M == 1) {
                    ans += M;
                    Licznik++;
                    i++;
                }
                else if(M == 2) {
                    ans += M - 1;
                    Licznik++;
                    i++;
                }
                else {
                    ans += M - 1;
                    Licznik += 2;
                    i++;
                }
            }
        }
        cout<<N-ans<<endl;
    }
    
    
    return 0;
}