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 #include #define ll long long using namespace std; void solve(){ ll n, f = -5, l = -5, strike = 0, one= 0; ll a, b; char tmp; priority_queueQ, E; cin >> n; bool tab[n+7]; for(int i = 1; i <= n; i++){ cin >> tmp; if(tmp == '1'){ tab[i] = 1; l = n - i; if(strike!=0 and f!=-5){ Q.push(strike); } strike = 0; if(f == -5) f = i -1; one++; } else{ tab[i] = 0; strike++; } } if(!one){cout << 0 << "\n"; return;} //cout << f << " " << l << "\n"; if(f!=-5 and f!=0) E.push(f); if(l!=0) E.push(l); int t = 0; int vacc = 0; while(!Q.empty() or !E.empty()){ if(!Q.empty()) a = Q.top() - 2*t; else a = -1e10; if(!E.empty()) b = E.top() - t; else b = -1e10; if(max(a,b) <= 0) break; if(a-2 > b or b <= 0){ Q.pop(); if(a > 2){ vacc += a-1; t+=2;} else{ vacc += a; t++;} } else{ E.pop(); vacc += b; t++; } //cout << a << " " << b << " " << vacc << "\n"; } cout << n - vacc << "\n"; } int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int q; cin >> q; for(int i = 0; i < q; i++){ solve(); } } /* 561 test 20 00010000010100101000 prawidlowa: 14 moja: 15 */