#include <iostream> #include <queue> int main() { std::ios_base::sync_with_stdio(0); int t, n, z, d, s, k, kk; char c; bool f; std::cin >> t; while (--t >= 0) { std::priority_queue<int> q; std::priority_queue<int> qq; std::cin >> n; z = 0; f = true; for (int i = 1; i <= n; ++i) { std::cin >> c; if (c == '0') { ++z; } else if (z > 0) { if (f) { q.push(z); f = false; } else { qq.push(z); } z = 0; } } if (z > 0) { q.push(z); } s = 0; d = 0; while (!qq.empty()) { kk = qq.top(); if (kk <= 2 * d) { qq.pop(); } else { if (q.empty() || kk - 2 * d - 2 >= q.top() - d) { ++s; qq.pop(); q.push(kk - d - 1); ++d; } else { k = q.top(); q.pop(); if (k > d) { s += k - d; ++d; } } } } while (!q.empty()) { k = q.top(); q.pop(); if (k > d) { s += k - d; ++d; } } std::cout << n - s << std::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 | #include <iostream> #include <queue> int main() { std::ios_base::sync_with_stdio(0); int t, n, z, d, s, k, kk; char c; bool f; std::cin >> t; while (--t >= 0) { std::priority_queue<int> q; std::priority_queue<int> qq; std::cin >> n; z = 0; f = true; for (int i = 1; i <= n; ++i) { std::cin >> c; if (c == '0') { ++z; } else if (z > 0) { if (f) { q.push(z); f = false; } else { qq.push(z); } z = 0; } } if (z > 0) { q.push(z); } s = 0; d = 0; while (!qq.empty()) { kk = qq.top(); if (kk <= 2 * d) { qq.pop(); } else { if (q.empty() || kk - 2 * d - 2 >= q.top() - d) { ++s; qq.pop(); q.push(kk - d - 1); ++d; } else { k = q.top(); q.pop(); if (k > d) { s += k - d; ++d; } } } } while (!q.empty()) { k = q.top(); q.pop(); if (k > d) { s += k - d; ++d; } } std::cout << n - s << std::endl; } return 0; } |