#include <iostream> #include <algorithm> #define ll long long using namespace std; ll t, n, i; pair<ll, bool> groups[100000];//..., is border char c; bool b[100000]; ll gr; ll x, y; ll r; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; for (int o = 0; o < t; ++o) { cin >> n; i = 0; gr = 0; x = 0; y = 0; r = 0; for (int j = 0; j < n; ++j) { cin >> c; b[j] = c == '1'; } for (; i < n; ++i) { if (b[i]) break; x++; } if (i == n) { cout << 0 << endl; continue; } groups[0] = { 2 * x, 1 }; gr = 1; x = 0; if (i == 0) i = 1; for (; i < n; ++i) { if (b[i]) { if (x > 0) { groups[gr] = { x, 0 }; gr++; x = 0; } } else x++; } groups[gr] = { 2 * x, 1 }; gr++; sort(groups, groups + gr, greater<pair<ll, bool>>()); for (int j = 0; j < gr; ++j) { groups[j].first -= 2*y; if (groups[j].first <= 0) break; if (groups[j].second) { y++; r += groups[j].first / 2; } else { y += 2; r += max(groups[j].first - 1, (ll)1); } } cout << n - r << endl; } }
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 | #include <iostream> #include <algorithm> #define ll long long using namespace std; ll t, n, i; pair<ll, bool> groups[100000];//..., is border char c; bool b[100000]; ll gr; ll x, y; ll r; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; for (int o = 0; o < t; ++o) { cin >> n; i = 0; gr = 0; x = 0; y = 0; r = 0; for (int j = 0; j < n; ++j) { cin >> c; b[j] = c == '1'; } for (; i < n; ++i) { if (b[i]) break; x++; } if (i == n) { cout << 0 << endl; continue; } groups[0] = { 2 * x, 1 }; gr = 1; x = 0; if (i == 0) i = 1; for (; i < n; ++i) { if (b[i]) { if (x > 0) { groups[gr] = { x, 0 }; gr++; x = 0; } } else x++; } groups[gr] = { 2 * x, 1 }; gr++; sort(groups, groups + gr, greater<pair<ll, bool>>()); for (int j = 0; j < gr; ++j) { groups[j].first -= 2*y; if (groups[j].first <= 0) break; if (groups[j].second) { y++; r += groups[j].first / 2; } else { y += 2; r += max(groups[j].first - 1, (ll)1); } } cout << n - r << endl; } } |