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
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second

using namespace std;

priority_queue<pair<int,int>> com;

int main()
{
    int t;
    scanf("%d",&t);
    for(int qq=0;qq<t;qq++){
        int n;
        int cz=0;
        char c;
        bool fo=true;
        scanf("%d\n",&n);
        for(int i=0;i<n;i++){
            scanf("%c",&c);
            if(c=='1'){
                if(fo){
                    com.push(mp(cz*10,1));
                    fo=false;
                } else {
                    com.push(mp(cz*5,2));
                }
                cz=0;
            } else {
                cz++;
            }
        }
        if(com.empty()){
            printf("0\n");
            continue;
        }
        com.push(mp(cz*10,1));

        int pans=0;
        int cou=0;
        pair<int,int> tmpp;
        while(!com.empty()){
            tmpp=com.top();
            com.pop();
            //printf("tmpp: %d %d\n",tmpp.fi,tmpp.se);
            if(tmpp.se==1){
                tmpp.fi/=10;
                pans+=max(0,tmpp.fi-cou);
                cou++;
            } else {
                tmpp.fi/=5;
                tmpp.fi=max(0,tmpp.fi-2*cou);
                if(tmpp.fi==0){
                    continue;
                }
                if(tmpp.fi==1){
                    pans++;
                    cou+=1;
                } else {
                    pans+=tmpp.fi-1;
                    cou+=2;
                }
            }
        }
        printf("%d\n",n-pans);
    }
    return 0;
}