#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ST first #define ND second #define SIZE(a) ((int)a.size()) void solve() { int n; string s; cin >> n >> s; int d = 0; vector<pii> v; bool start = true; int res = 0; for(int i=0; i < SIZE(s); i++) { char c = s[i]; if(c == '0') { d++; } else { res++; if(start) { v.push_back({2*d, d}); start = false; } else { v.push_back({d, d}); } d = 0; } } v.push_back({2*d, d}); sort(v.begin(), v.end(), greater<pii>()); int day=0; for(pii x : v) { // cout << x.first << " " << x.second << "\n"; if(x.first == x.second) { int diff = x.first - 2*day; if(diff > 2) { res+=2*day+1; day+=2; } else if(diff > 0) { res+=x.first-1; day+=1; } else { res+=x.first; } } else { int diff = x.second - day; if(diff > 0) { res+=day; day+=1; } else { res+=x.second; } } } cout << res << "\n"; } int main() { ios_base::sync_with_stdio(0); int t; cin >> t; while(t--) { solve(); } }
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 | #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ST first #define ND second #define SIZE(a) ((int)a.size()) void solve() { int n; string s; cin >> n >> s; int d = 0; vector<pii> v; bool start = true; int res = 0; for(int i=0; i < SIZE(s); i++) { char c = s[i]; if(c == '0') { d++; } else { res++; if(start) { v.push_back({2*d, d}); start = false; } else { v.push_back({d, d}); } d = 0; } } v.push_back({2*d, d}); sort(v.begin(), v.end(), greater<pii>()); int day=0; for(pii x : v) { // cout << x.first << " " << x.second << "\n"; if(x.first == x.second) { int diff = x.first - 2*day; if(diff > 2) { res+=2*day+1; day+=2; } else if(diff > 0) { res+=x.first-1; day+=1; } else { res+=x.first; } } else { int diff = x.second - day; if(diff > 0) { res+=day; day+=1; } else { res+=x.second; } } } cout << res << "\n"; } int main() { ios_base::sync_with_stdio(0); int t; cin >> t; while(t--) { solve(); } } |