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

using namespace std;
#define endl '\n'
#define fi first
#define sc second
#define LL long long

int main(){
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        string Input;
        cin >> Input;
        priority_queue<int> Singles;
        priority_queue<int> Doubles;
        int x = 0;
        bool F = true;
        for(int i = 0; i < N; i++){
            if(Input[i] == '1'){
                if(F && x != 0){
                    Singles.push(x);
                }
                else if(x != 0){
                    Doubles.push(x);
                }
                x = 0;
                F = false;
            }
            else{
                x++;
            }
        }
        if(x != 0){
            Singles.push(x);
        }
        F = false;
        int k = 0, Result = N;
        /*cout << "Singles: ";
        while(!Singles.empty()){
            cout << Singles.top() << " ";
            Singles.pop();
        }
        cout << endl << "Doubles: ";
        while(!Doubles.empty()){
            cout << Doubles.top() << " ";
            Doubles.pop();
        }
        cout << endl;*/
        while(!F){
            int a = 0, b = 0;
            if(!Singles.empty()) a = Singles.top() - k;
            if(!Doubles.empty()) b = Doubles.top() - 2 * k;
            //cout << a << " " << b << endl;
            if(a > 0 && (a >= b - 1) ){
                Singles.pop();
                Result -= a;
            }
            else if(b > 0 && b >= a){
                Doubles.pop();
                Result--;
                Singles.push(b + k - 1);
            }
            else F = true;

            k++;
        }
        cout << Result << endl;
    }
    return 0;
}