#include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(NULL); int n,t; cin >> t; string s; while (t--) { cin >> n; cin >> s; //cout << n << ' ' << s << endl; int i=0; int c = 0; vector<pair<int,int>> v; while (i<n && s[i]=='0') {c++; i++;} if (i==n) { cout << "0\n"; continue; } if (c!=0) v.emplace_back(c*2,1); c=0; int k = n-1; while (k>i && s[k]=='0') {k--; c++;} v.emplace_back(c*2,1); if (c!=0) c=0; k++; for (i++;i<k;i++) { if (s[i]=='0') c++; else { if (c!=0) v.emplace_back(c,2); c=0; } } std::sort(v.begin(), v.end(), std::greater()); int step = 0; int saved = 0; for (auto const& p : v) { //cout << step << ' ' << saved << ' ' << p.first << ' ' << p.second << endl; int a = p.first; if (p.second == 1) { a/=2; if (a<=step) break; saved += a-step; }else { if (a<=2*step) break; a-=step*2; if (a==1) saved++; else { saved += a-1; step++; } } step++; } 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 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 <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(NULL); int n,t; cin >> t; string s; while (t--) { cin >> n; cin >> s; //cout << n << ' ' << s << endl; int i=0; int c = 0; vector<pair<int,int>> v; while (i<n && s[i]=='0') {c++; i++;} if (i==n) { cout << "0\n"; continue; } if (c!=0) v.emplace_back(c*2,1); c=0; int k = n-1; while (k>i && s[k]=='0') {k--; c++;} v.emplace_back(c*2,1); if (c!=0) c=0; k++; for (i++;i<k;i++) { if (s[i]=='0') c++; else { if (c!=0) v.emplace_back(c,2); c=0; } } std::sort(v.begin(), v.end(), std::greater()); int step = 0; int saved = 0; for (auto const& p : v) { //cout << step << ' ' << saved << ' ' << p.first << ' ' << p.second << endl; int a = p.first; if (p.second == 1) { a/=2; if (a<=step) break; saved += a-step; }else { if (a<=2*step) break; a-=step*2; if (a==1) saved++; else { saved += a-1; step++; } } step++; } cout << n - saved << '\n'; } } |