#include <bits/stdc++.h> using namespace std; int t; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>t; for(int i=0;i<t;i++) { int n, d=0, rsc=0; vector<pair<int, int> >V; cin>>n; int cnt=0; for(int u=0;u<n;u++) { char x; cin>>x; if(x=='0')cnt++; else if(cnt!=0) { if(V.empty())V.push_back(make_pair(2*cnt, 1)); else V.push_back(make_pair(cnt, 2)); cnt=0; } } if(cnt!=0)V.push_back(make_pair(2*cnt, 1)); if(V.size()==1&&V[0].first==2*n) { cout<<0<<endl; continue; } sort(V.begin(), V.end()); for(int u=V.size()-1;u>=0;u--) { if(V[u].second==1&&V[u].first>2*d) { rsc+=V[u].first/2-d; d++; } else if(V[u].first>2*d) { int pom=V[u].first-2*d-1; if(pom>1){ d+=2; rsc+=pom; } else { rsc+=1; d+=1; } } else break; } cout<<n-rsc<<endl; } return 0; }
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 | #include <bits/stdc++.h> using namespace std; int t; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>t; for(int i=0;i<t;i++) { int n, d=0, rsc=0; vector<pair<int, int> >V; cin>>n; int cnt=0; for(int u=0;u<n;u++) { char x; cin>>x; if(x=='0')cnt++; else if(cnt!=0) { if(V.empty())V.push_back(make_pair(2*cnt, 1)); else V.push_back(make_pair(cnt, 2)); cnt=0; } } if(cnt!=0)V.push_back(make_pair(2*cnt, 1)); if(V.size()==1&&V[0].first==2*n) { cout<<0<<endl; continue; } sort(V.begin(), V.end()); for(int u=V.size()-1;u>=0;u--) { if(V[u].second==1&&V[u].first>2*d) { rsc+=V[u].first/2-d; d++; } else if(V[u].first>2*d) { int pom=V[u].first-2*d-1; if(pom>1){ d+=2; rsc+=pom; } else { rsc+=1; d+=1; } } else break; } cout<<n-rsc<<endl; } return 0; } |