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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <queue>
using namespace std;
string s;
priority_queue<int> K;
int M[1000020];
int main()
{
    std::ios_base::sync_with_stdio(0);
    int T,n;
    cin>>T;
    while(T--)
    {
        cin>>n;
        cin>>s;
        int ost_niezerowy=2; //zaszczepione
        int wart_k=0;
        int wart_m=0;
        int ind_m=0;
        
        //10001000
        for (int i=0; i<n; i++)
        {
            if (ost_niezerowy==2 && s[i]=='0')
                wart_k++;
            if (ost_niezerowy==1 && s[i]=='0')
                wart_m++;
            if (s[i]=='1')
            {
                if (ost_niezerowy==2)
                {
                    ost_niezerowy=1;
                    if (wart_k==0)
                        continue;
                    K.push(wart_k);
                    ost_niezerowy=1;
                    wart_k=0;
                }
                if (ost_niezerowy==1)
                {
                    ost_niezerowy=1;
                    if (wart_m==0)
                        continue;
                    M[ind_m]=wart_m;
                    ind_m++;
                    ost_niezerowy=1;
                    wart_m=0;
                }
            }
        }
        if (wart_m>0)
            K.push(wart_m);
   
        if (wart_k>0)
            K.push(wart_k);
            
        
        sort(M,M+ind_m);
        int tura=0;
        
        int Gen_wynik=0;
               
        for (int i=ind_m-1; i>=0; i--)
        {
            int a_m=M[i];
            a_m-=2*tura;
            if (a_m<=0)
               break;
            
            if (K.empty() || K.top()-tura<=0 || a_m-2>K.top()-tura) //przerzuć m do k
            {
                if (a_m-1+tura>0)
                    K.push(a_m-1+tura);
                Gen_wynik+=1;
            }
            else
            {
                i++;
                Gen_wynik+=K.top()-tura;
                K.pop();
            }
            tura++;
        }
        
        while(!K.empty())
        {
            Gen_wynik+=max(0,K.top()-tura);
            tura++;
             K.pop();
        }
        cout<<n-Gen_wynik<<"\n";
    }
    return 0;
}