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 #include using namespace std; using ll = long long; char s[100001]; int solve(int n) { if (n == 1) { return s[0] == '0'; } deque> v; for (int i = 0; i < n;) { if (s[i] == '0') { int j = i + 1; while (j < n && s[j] == '0') { j++; } v.emplace_back(j-i, 2); i = j; } else { i++; } } if (v.empty()) { return 0; } if (s[0] == '0') { v.front().second--; } if (s[n-1] == '0') { v.back().second--; } if (v.back().second == 0) { return n; } vector ones; if (v.front().second == 1) { ones.push_back(v.front().first); v.pop_front(); } if (!v.empty() && v.back().second == 1) { ones.push_back(v.back().first); v.pop_back(); } if (ones.size() == 2 && ones[0] < ones[1]) { swap(ones[0], ones[1]); } sort(v.begin(), v.end(), greater>()); int res = 0; int days = 0; for(int i = 0, j = 0; i < v.size() || j < ones.size();) { if (i == v.size()) { if (ones[j] > days) { res += ones[j] - days; days++; } j++; } else if (j == ones.size()) { int r = v[i].first - 2 * days; if (r == 1 || r == 2) { res++; days++; } else if (r > 2) { res += v[i].first - 2 * days - 1; days += 2; } i++; } else { if (v[i].first - 2 * days - 2 > ones[j] - days) { int r = v[i].first - 2 * days; if (r == 1 || r == 2) { res++; days++; } else if (r > 2) { res += v[i].first - 2 * days - 1; days += 2; } i++; } else { if (ones[j] > days) { res += ones[j] - days; days++; } j++; } } } return res; } int main() { int z; scanf("%d", &z); while (z--) { int n; scanf("%d", &n); scanf("%s", s); printf("%d\n", n - solve(n)); } }