#include <iostream> #include <queue> #include <algorithm> using namespace std; int main() { int t; cin >> t; for (int i = 0; i < t; i++) { int n, right, left = -1, zeros = 0; priority_queue<int> q; char c; bool disease = false; cin >> n; cin.get(c); for (int j = 0; j < n; j++) { cin.get(c); if (c == '0') { zeros++; } else { if (left == -1) { left = zeros; } else if (zeros > 0) { q.push(zeros); } zeros = 0; disease = true; } } right = zeros; if (!disease) { cout << 0 << endl; } else { int d = 0; int vacined = 0; while (left - d > 0 || (!q.empty() && q.top() - 2*d > 0) || right - d > 0) { int ll = max(left - d, 0); int rr = max(right - d, 0); if (q.empty()) { if (ll > rr) { vacined += ll; left = 0; } else { vacined += rr; right = 0; } } else { int qq = max(q.top() - 2*d, 0); if (ll == 0 && rr == 0) { if (qq == 1 || qq == 2) { vacined += 1; } else { vacined += qq - 1; d++; } q.pop(); } else if (ll == 0 && qq == 0) { vacined += rr; right = 0; } else if (rr == 0 && qq == 0) { vacined += ll; left = 0; } else if (ll == 0) { if (qq >= 4) { vacined += qq - 1; d++; } else { vacined += rr; right = 0; } } else if (rr == 0) { if (qq >= 4) { vacined += qq - 1; d++; } else { vacined += ll; left = 0; } } else if (qq == 0) { vacined += ll + rr - 1; left = 0; right = 0; } else { if (ll + rr > qq) { vacined += ll + rr - 1; left = 0; right = 0; d++; if (ll == 1 || rr == 1) { d--; } } else { if (qq == 1 || qq == 2) { vacined += 1; } else { vacined += qq - 1; d++; } q.pop(); } } } d++; } cout << n - vacined << endl; } } 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 111 112 113 114 115 116 117 118 119 120 121 122 | #include <iostream> #include <queue> #include <algorithm> using namespace std; int main() { int t; cin >> t; for (int i = 0; i < t; i++) { int n, right, left = -1, zeros = 0; priority_queue<int> q; char c; bool disease = false; cin >> n; cin.get(c); for (int j = 0; j < n; j++) { cin.get(c); if (c == '0') { zeros++; } else { if (left == -1) { left = zeros; } else if (zeros > 0) { q.push(zeros); } zeros = 0; disease = true; } } right = zeros; if (!disease) { cout << 0 << endl; } else { int d = 0; int vacined = 0; while (left - d > 0 || (!q.empty() && q.top() - 2*d > 0) || right - d > 0) { int ll = max(left - d, 0); int rr = max(right - d, 0); if (q.empty()) { if (ll > rr) { vacined += ll; left = 0; } else { vacined += rr; right = 0; } } else { int qq = max(q.top() - 2*d, 0); if (ll == 0 && rr == 0) { if (qq == 1 || qq == 2) { vacined += 1; } else { vacined += qq - 1; d++; } q.pop(); } else if (ll == 0 && qq == 0) { vacined += rr; right = 0; } else if (rr == 0 && qq == 0) { vacined += ll; left = 0; } else if (ll == 0) { if (qq >= 4) { vacined += qq - 1; d++; } else { vacined += rr; right = 0; } } else if (rr == 0) { if (qq >= 4) { vacined += qq - 1; d++; } else { vacined += ll; left = 0; } } else if (qq == 0) { vacined += ll + rr - 1; left = 0; right = 0; } else { if (ll + rr > qq) { vacined += ll + rr - 1; left = 0; right = 0; d++; if (ll == 1 || rr == 1) { d--; } } else { if (qq == 1 || qq == 2) { vacined += 1; } else { vacined += qq - 1; d++; } q.pop(); } } } d++; } cout << n - vacined << endl; } } return 0; } |