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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//author Karolina Miśkiewicz
#include<bits/stdc++.h>
using namespace std;
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   int n;
   cin >> n;
   for(int li = 0; li < n; li++)
   {
       int d;
       cin >> d;
       string s;
       cin >> s;
       int z = 0;
       vector<int> q, b;
       for(int i = 0; i < d; i++)
       {
           if(s[i] == '0')
               z++;
           else
           {
               if(z > 0)
               {
                   if(b.empty() && s[0]== '0')
                   {
                       b.push_back(z);
                   }
                   else
                       q.push_back(z);
                   z = 0;
               }
           }
       }
 
       if(z > 0)
       {
           b.push_back(z);
       }
       int w = 0, ok=0;
       sort(q.begin(), q.end());
       sort(b.begin(), b.end());
 
       while(!q.empty())
       {
           int temp;

            if(!b.empty())
            {
                if(b.size() == 2)
                {
                    int spr, spr2;
                    if(q[q.size()-1] - (2*(w+2)) == 1)
                        spr = 1;
                    else
                        spr = q[q.size()-1] - ((w+2)*2 + 1);

                    if(q[q.size()-1] - w*2 == 1)
                        spr2 = 1;
                    else 
                        spr2 = q[q.size()-1] - ((w*2) + 1);

                    if(b[0] - w + b[1] - (w+1) + spr > spr2 + b[0] - (w+2) + b[1] - (w+3) && b[0] - w + b[1] - (w+1) + spr > spr2 && b[0] - w + b[1] - (w+1) + spr >= b[1] - (w+1) + spr2)
                    {

                        if(b[1] + b[0] - (2*w + 1) > 0)
                        {
                            ok += b[1] + b[0] - (2*w + 1);
                            w+=2;
                        }
                        b.pop_back();
                        b.pop_back();
                        continue;
                    }
                    else if(b[1] - (w + 1) >= q[q.size()-1] - (w + 1)*2)
                    {
                        if(b[1] - w > 0)
                        {
                            ok += b[1] - w;
                            w++; 
                        }
                        b.pop_back();
                        continue;
                    }
                }
                else//bsize == 1
                {
                    if(b[0] - (w + 1) >= q[q.size()-1] - (w+1)*2)
                    {
                        if(b[0] - w > 0)
                        {
                            ok += b[0]-w;
                            w++;
                        }
                        b.pop_back();
                        continue;
                    }
                }
            }

            temp = q[q.size()-1];
            q.pop_back();
            if(temp - w*2 > 0)
           {
               if(temp - w*2 > 2)
               {
                   
                    ok += temp - (w*2 + 1);
                    w += 2;
                   
               }
               else
               {
                   ok +=  1;
                   w += 1;
               }
           }
           else
           {
               break;
           }
       }

       while(!b.empty())
        {
            int temp = b[b.size()-1];
            b.pop_back();
            if(temp - w > 0)
            {
                ok += temp - w;
                w += 1;
            }
        }
       int wynik = d - ok;
       cout << wynik << "\n";
   }
}