#include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif //const int NMAX = 1e5 + 7; int n, zz, t, res; string s; vector<int> przedzialy; priority_queue<int> skrajne, wewnetrzne; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> zz; for (int ii = 0; ii < zz; ++ii) { cin >> n >> s; int l = 0; for (int i = 0; i < (int) s.size(); ++i) { if (s[i] == '0') { l++; } else if (l > 0) { przedzialy.push_back(l); l = 0; } } if (l > 0) { przedzialy.push_back(l); } int begin = 0, end = 0; if (przedzialy.empty()) { cout << n << "\n"; goto clear; } if (s[0] == '0') { skrajne.push(przedzialy[0]); begin = 1; } if (przedzialy.size() > begin && s.back() == '0') { skrajne.push(przedzialy.back()); end = 1; } for (int i = begin; i < (int) przedzialy.size() - end; ++i) { wewnetrzne.push(przedzialy[i]); } while (true) { if (!skrajne.empty() && !wewnetrzne.empty()) { if (2 * skrajne.top() >= wewnetrzne.top()) { if (skrajne.top() - t <= 0) { break; } res += skrajne.top() - t; skrajne.pop(); t++; } else { if (wewnetrzne.top() - 2 * t - (wewnetrzne.top() - 2 * t > 1) <= 0) { break; } res += wewnetrzne.top() - 2 * t - (wewnetrzne.top() - 2 * t > 1); t += 1 + (wewnetrzne.top() - 2 * t > 1); wewnetrzne.pop(); } } else if (!wewnetrzne.empty()) { if (wewnetrzne.top() - 2 * t - (wewnetrzne.top() - 2 * t > 1) <= 0) { break; } res += wewnetrzne.top() - 2 * t - (wewnetrzne.top() - 2 * t > 1); t += 1 + (wewnetrzne.top() - 2 * t > 1); wewnetrzne.pop(); } else if (!skrajne.empty()) { if (skrajne.top() - t <= 0) { break; } res += skrajne.top() - t; skrajne.pop(); t++; } else { break; } } cout << s.size() - res << "\n"; clear: while (!skrajne.empty()) { skrajne.pop(); } while (!wewnetrzne.empty()) { wewnetrzne.pop(); } przedzialy.clear(); t = res = 0; } 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 100 101 102 103 104 105 106 107 108 109 110 | #include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif //const int NMAX = 1e5 + 7; int n, zz, t, res; string s; vector<int> przedzialy; priority_queue<int> skrajne, wewnetrzne; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> zz; for (int ii = 0; ii < zz; ++ii) { cin >> n >> s; int l = 0; for (int i = 0; i < (int) s.size(); ++i) { if (s[i] == '0') { l++; } else if (l > 0) { przedzialy.push_back(l); l = 0; } } if (l > 0) { przedzialy.push_back(l); } int begin = 0, end = 0; if (przedzialy.empty()) { cout << n << "\n"; goto clear; } if (s[0] == '0') { skrajne.push(przedzialy[0]); begin = 1; } if (przedzialy.size() > begin && s.back() == '0') { skrajne.push(przedzialy.back()); end = 1; } for (int i = begin; i < (int) przedzialy.size() - end; ++i) { wewnetrzne.push(przedzialy[i]); } while (true) { if (!skrajne.empty() && !wewnetrzne.empty()) { if (2 * skrajne.top() >= wewnetrzne.top()) { if (skrajne.top() - t <= 0) { break; } res += skrajne.top() - t; skrajne.pop(); t++; } else { if (wewnetrzne.top() - 2 * t - (wewnetrzne.top() - 2 * t > 1) <= 0) { break; } res += wewnetrzne.top() - 2 * t - (wewnetrzne.top() - 2 * t > 1); t += 1 + (wewnetrzne.top() - 2 * t > 1); wewnetrzne.pop(); } } else if (!wewnetrzne.empty()) { if (wewnetrzne.top() - 2 * t - (wewnetrzne.top() - 2 * t > 1) <= 0) { break; } res += wewnetrzne.top() - 2 * t - (wewnetrzne.top() - 2 * t > 1); t += 1 + (wewnetrzne.top() - 2 * t > 1); wewnetrzne.pop(); } else if (!skrajne.empty()) { if (skrajne.top() - t <= 0) { break; } res += skrajne.top() - t; skrajne.pop(); t++; } else { break; } } cout << s.size() - res << "\n"; clear: while (!skrajne.empty()) { skrajne.pop(); } while (!wewnetrzne.empty()) { wewnetrzne.pop(); } przedzialy.clear(); t = res = 0; } return 0; } |