#include <iostream> #include <queue> int t, n; std::priority_queue<int> m; int start, end; void input() { std::string s; std::cin >> n >> s; int k = 0; int i = 0; start = -1; end = -1; while (i < n) { if (s[i] == '0') { ++k; } else if (start == -1) { start = k; k = 0; } else if (k > 0) { m.push(k); k = 0; } ++i; } end = k; } int max(int i, int j) { return i > j ? i : j; } int solve(bool e, bool s) { std::priority_queue<int> Q = m; if (start == -1) { return 0; } int result = 0; int i = 0; if (e && end - i > 0) { result += end - i; ++i; } if (s && start - i > 0) { result += start - i; ++i; } while (!Q.empty()) { int q = Q.top(); Q.pop(); int qq = q - 2 * i; int ii = 2; if (qq == 1) { ii = 1; } else { qq -= 1; } if (qq <= 0) { break; } result += qq; i += ii; } return n - result; } int min(int a, int b) { return a < b ? a : b; } int solve() { int res = min( min(solve(false, false), solve(false, true)), min(solve(true, false), solve(true, true)) ); while (!m.empty()) { m.pop(); } return res; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cin >> t; while (t--) { input(); std::cout << solve() << "\n"; } 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 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 | #include <iostream> #include <queue> int t, n; std::priority_queue<int> m; int start, end; void input() { std::string s; std::cin >> n >> s; int k = 0; int i = 0; start = -1; end = -1; while (i < n) { if (s[i] == '0') { ++k; } else if (start == -1) { start = k; k = 0; } else if (k > 0) { m.push(k); k = 0; } ++i; } end = k; } int max(int i, int j) { return i > j ? i : j; } int solve(bool e, bool s) { std::priority_queue<int> Q = m; if (start == -1) { return 0; } int result = 0; int i = 0; if (e && end - i > 0) { result += end - i; ++i; } if (s && start - i > 0) { result += start - i; ++i; } while (!Q.empty()) { int q = Q.top(); Q.pop(); int qq = q - 2 * i; int ii = 2; if (qq == 1) { ii = 1; } else { qq -= 1; } if (qq <= 0) { break; } result += qq; i += ii; } return n - result; } int min(int a, int b) { return a < b ? a : b; } int solve() { int res = min( min(solve(false, false), solve(false, true)), min(solve(true, false), solve(true, true)) ); while (!m.empty()) { m.pop(); } return res; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cin >> t; while (t--) { input(); std::cout << solve() << "\n"; } return 0; } |