#include<bits/stdc++.h> using namespace std; #define d(a)cout<<#a<<" = "<<a<<"\n"; //#define f first //#define s second #define mp make_pair #define TURBO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long vector<int>health; int main(){ TURBO; int t; cin>>t; while (t--) { health.clear(); int n; string s; cin>>n; cin>>s; int first=-1,last=-1,cur=0; for(int i=0;i<n;i++){ bool x=(s[i]=='1'); if(x){ if(first==-1)first=cur; else if(cur)health.push_back(cur); cur=0; } else cur++; if(i+1==n)last=cur; //d(cur); } health.push_back(0); sort(health.begin(),health.end(),greater<int>()); int wyleczone=0; int zatrute=0; //bool f=1,l=1; //d((health[0]==1 and first<1 and last<1)) if(health.size())if(health[0]==1 and first<1 and last<1)wyleczone++; //d(last);d(first);for(auto i:health)d(i); for(int i=0;i<health.size();){ //d(health[i]); int h=max(max(first-zatrute,last-zatrute),health[i]-zatrute-zatrute-1); //d(h) if(h>0) wyleczone+=h; else break; if(h==first){ zatrute++; first=0; } else if(h==last){ zatrute++; last=0; } else{ i++; zatrute+=2; } } cout<<n-wyleczone<<"\n"; } } /* 3 8 00110100 10 1001000010 4 0000 */
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 | #include<bits/stdc++.h> using namespace std; #define d(a)cout<<#a<<" = "<<a<<"\n"; //#define f first //#define s second #define mp make_pair #define TURBO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long vector<int>health; int main(){ TURBO; int t; cin>>t; while (t--) { health.clear(); int n; string s; cin>>n; cin>>s; int first=-1,last=-1,cur=0; for(int i=0;i<n;i++){ bool x=(s[i]=='1'); if(x){ if(first==-1)first=cur; else if(cur)health.push_back(cur); cur=0; } else cur++; if(i+1==n)last=cur; //d(cur); } health.push_back(0); sort(health.begin(),health.end(),greater<int>()); int wyleczone=0; int zatrute=0; //bool f=1,l=1; //d((health[0]==1 and first<1 and last<1)) if(health.size())if(health[0]==1 and first<1 and last<1)wyleczone++; //d(last);d(first);for(auto i:health)d(i); for(int i=0;i<health.size();){ //d(health[i]); int h=max(max(first-zatrute,last-zatrute),health[i]-zatrute-zatrute-1); //d(h) if(h>0) wyleczone+=h; else break; if(h==first){ zatrute++; first=0; } else if(h==last){ zatrute++; last=0; } else{ i++; zatrute+=2; } } cout<<n-wyleczone<<"\n"; } } /* 3 8 00110100 10 1001000010 4 0000 */ |