#include <bits/stdc++.h> using namespace std; #ifdef LOCAL template<class T, class U> ostream& operator<<(ostream& os, pair<T, U> p) { return os << "(" << p.first << ", " << p.second << ")"; } template<class C, class = typename C::value_type> typename enable_if<!is_same<C, string>::value, ostream&>::type operator<<(ostream& os, C c) { for (auto i = c.begin(); i != c.end(); i++) { os << " {"[i == c.begin()] << *i << ",}"[next(i) == c.end()]; } return os; } #define debug(x) { cerr << #x << " = " << x << endl; } #else #define debug(...) {} #endif void build(const string &s, vector<int> &two, queue<int> &one) { int group = 0; bool first = true; vector<int> tmp; for (char c : s) { if (c == '1') { if (group > 0) { if (first) { tmp.push_back(group); } else { two.push_back(group); } } group = 0; first = false; } else { group++; } } if (group > 0) { tmp.push_back(group); } sort(tmp.begin(), tmp.end(), greater<int>()); for (int x : tmp) { one.push(x); } } int solve(int n, string s) { int count_ones = count(s.begin(), s.end(), '1'); if (count_ones == 0) { return 0; } vector<int> two; queue<int> one; build(s, two, one); sort(two.begin(), two.end()); int t = 0; int next_two = int(two.size()) - 1; int res = 0; while (next_two >= 0 || !one.empty()) { debug("STEP"); while (!one.empty() && (one.front() - t <= 0 || (one.front() - t == 1 && (one.size() >= 2 || (next_two >= 0 && two[next_two] - 2 * t > 0))))) { one.pop(); } if (!one.empty()) { debug("one"); debug(one.front() - t); res += one.front() - t; one.pop(); } else { debug("two"); if (next_two < 0) { break; } int g = two[next_two]; next_two--; if (g - 2 * t <= 0) { break; } res++; debug(res); if (g - 2 * t >= 3) { debug(g - t - 1); one.push(g - t - 1); } } t++; } return n - res; } int main() { ios_base::sync_with_stdio(false); int t; cin >> t; while (t--) { int n; string s; cin >> n >> s; cout << solve(n, s) << "\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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | #include <bits/stdc++.h> using namespace std; #ifdef LOCAL template<class T, class U> ostream& operator<<(ostream& os, pair<T, U> p) { return os << "(" << p.first << ", " << p.second << ")"; } template<class C, class = typename C::value_type> typename enable_if<!is_same<C, string>::value, ostream&>::type operator<<(ostream& os, C c) { for (auto i = c.begin(); i != c.end(); i++) { os << " {"[i == c.begin()] << *i << ",}"[next(i) == c.end()]; } return os; } #define debug(x) { cerr << #x << " = " << x << endl; } #else #define debug(...) {} #endif void build(const string &s, vector<int> &two, queue<int> &one) { int group = 0; bool first = true; vector<int> tmp; for (char c : s) { if (c == '1') { if (group > 0) { if (first) { tmp.push_back(group); } else { two.push_back(group); } } group = 0; first = false; } else { group++; } } if (group > 0) { tmp.push_back(group); } sort(tmp.begin(), tmp.end(), greater<int>()); for (int x : tmp) { one.push(x); } } int solve(int n, string s) { int count_ones = count(s.begin(), s.end(), '1'); if (count_ones == 0) { return 0; } vector<int> two; queue<int> one; build(s, two, one); sort(two.begin(), two.end()); int t = 0; int next_two = int(two.size()) - 1; int res = 0; while (next_two >= 0 || !one.empty()) { debug("STEP"); while (!one.empty() && (one.front() - t <= 0 || (one.front() - t == 1 && (one.size() >= 2 || (next_two >= 0 && two[next_two] - 2 * t > 0))))) { one.pop(); } if (!one.empty()) { debug("one"); debug(one.front() - t); res += one.front() - t; one.pop(); } else { debug("two"); if (next_two < 0) { break; } int g = two[next_two]; next_two--; if (g - 2 * t <= 0) { break; } res++; debug(res); if (g - 2 * t >= 3) { debug(g - t - 1); one.push(g - t - 1); } } t++; } return n - res; } int main() { ios_base::sync_with_stdio(false); int t; cin >> t; while (t--) { int n; string s; cin >> n >> s; cout << solve(n, s) << "\n"; } } |