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
#include <iostream>
#include <queue>

using namespace std;

struct Odcinek {
    int first, second;
};

inline bool operator < (const Odcinek &a, const Odcinek &b) {
    return a.first *b.second < b.first * a.second;
}
priority_queue <Odcinek> kol;// first - dl, second - odejmij

int main()
{
    ios_base::sync_with_stdio(0); cin.tie();
    int T;
    cin>>T;
    for(int t=0;t!=T;t++) {
        int n,l=0,tura=0, wyn=0; string s;
        cin >> n >> s;
        for(int i=0;i!=n;i++) {
            if(s[i] == '0') l++;
            else if(l > 1 || (i > 0 &&  s[i-1] == '0')) {
                if(kol.empty() && s[0] == '0')
                    kol.push({l,1});
                else
                    kol.push({l,2});
                l=0;
            }
        } if(s[n-1] == '0')
            kol.push({l,1});
        while(!kol.empty()) {
            Odcinek a = kol.top();
            kol.pop();
            if(a.first - a.second*tura <= 0)
                continue;
            a.first -= tura + 1;
            wyn++;
            if(a.second == 1)
                wyn += a.first;
            else {
                a.second = 1;
                if(a.first > 0)
                    kol.push(a);
            }
            tura++;
        }
        cout<<n-wyn<<"\n";
    }
    return 0;
}