#include<bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; string str; cin>>str; vector<array<int, 3>> gaps; int last = -1; for(int i = 0; i < n; i++){ if(str[i] == '1'){ if(last != i-1){ if(last == -1){ gaps.push_back({i, i, 0}); }else{ gaps.push_back({(i-last)/2, i - last - 1, 1}); } } last = i; } } if(last != n-1)gaps.push_back({n-1 - last, n-1-last, 0}); //for(auto p : gaps)cout<<p.first<<" "<<p.second<<"\n"; sort(gaps.begin(), gaps.end(), greater<array<int, 3>>()); int saved = 0; int time = 0; for(int i = 0; i < gaps.size(); i++){ if(gaps[i][2] == 0){ int left = gaps[i][1] - time; if(left > 0){ time++; saved += left; } }else{ int left = gaps[i][1] - 2 * time; if(left >= 3){ time += 2; saved += left-1; }else if(left > 0){ time++; saved++; } } } cout<<(n - saved)<<"\n"; } }
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 | #include<bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; string str; cin>>str; vector<array<int, 3>> gaps; int last = -1; for(int i = 0; i < n; i++){ if(str[i] == '1'){ if(last != i-1){ if(last == -1){ gaps.push_back({i, i, 0}); }else{ gaps.push_back({(i-last)/2, i - last - 1, 1}); } } last = i; } } if(last != n-1)gaps.push_back({n-1 - last, n-1-last, 0}); //for(auto p : gaps)cout<<p.first<<" "<<p.second<<"\n"; sort(gaps.begin(), gaps.end(), greater<array<int, 3>>()); int saved = 0; int time = 0; for(int i = 0; i < gaps.size(); i++){ if(gaps[i][2] == 0){ int left = gaps[i][1] - time; if(left > 0){ time++; saved += left; } }else{ int left = gaps[i][1] - 2 * time; if(left >= 3){ time += 2; saved += left-1; }else if(left > 0){ time++; saved++; } } } cout<<(n - saved)<<"\n"; } } |