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
#include <iostream>
#include <vector>
#include <algorithm>
int t,n;
char x;
int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin>>t;
    for(int tt=0;tt<t;tt++){
        std::cin>>n;
        bool first=true;
        std::vector<int> dl;
        int acc=0;
        for(int i=0;i<n;i++){
            std::cin>>x;
            if(x=='0'){
                acc++;
            }else{
                if(first){
                    first=false;
                    dl.emplace_back(acc*2);
                }else{
                    dl.push_back(acc);
                    dl.push_back(acc);
                }
                acc=0;
            }
            
        }
        dl.emplace_back(acc*2);
        dl.emplace_back(0);
        dl.emplace_back(0);
        sort(dl.begin(),dl.end(),std::greater<int>());
        int day=0;
        int result=0;
        while(dl[day]>day*2){
            result+=dl[day]-day*2;
            day++;
        }
        std::cout<<n-(result+1)/2<<std::endl;
    }
    

}