#include <algorithm> #include <iostream> #include <string.h> using namespace std; #define N 100000 int intervals[(N + 1) * 2]; int edges[2]; int solve() { int n, i = -1, j; int d, maxd = 0, aktd; int saved = 0, vacc = 0; char c; cin >> n; memset(intervals, 0, sizeof(intervals)); for (j = 0; j < n; j++) { cin >> c; if (c == '0') continue; d = j - i - 1; if (i == -1) { d *= 2; edges[0] = d; } i = j; intervals[d] += 1; maxd = max(d, maxd); } if (i == -1) return 0; d = (n - i - 1) * 2; edges[1] = d; intervals[d] += 1; maxd = max(d, maxd); for (d = maxd; d > 0; d--) { if (intervals[d] == 0) continue; div_t dd = div(d, 2); for (i = 0; i < 2 && intervals[d] > 0 && (aktd = dd.quot - vacc) > 0; i++) { if (d != edges[i]) continue; intervals[d] -= 1; saved += aktd; vacc += 1; } while (intervals[d] > 0 && (aktd = d - 2 * vacc) > 0) { vacc += min(aktd, 2); saved += max(aktd - 1, 1); intervals[d] -= 1; } } return n - saved; } int main() { ios_base::sync_with_stdio(0); int t; cin >> t; for (int k = 0; k < t; k++) { cout << solve() << 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 | #include <algorithm> #include <iostream> #include <string.h> using namespace std; #define N 100000 int intervals[(N + 1) * 2]; int edges[2]; int solve() { int n, i = -1, j; int d, maxd = 0, aktd; int saved = 0, vacc = 0; char c; cin >> n; memset(intervals, 0, sizeof(intervals)); for (j = 0; j < n; j++) { cin >> c; if (c == '0') continue; d = j - i - 1; if (i == -1) { d *= 2; edges[0] = d; } i = j; intervals[d] += 1; maxd = max(d, maxd); } if (i == -1) return 0; d = (n - i - 1) * 2; edges[1] = d; intervals[d] += 1; maxd = max(d, maxd); for (d = maxd; d > 0; d--) { if (intervals[d] == 0) continue; div_t dd = div(d, 2); for (i = 0; i < 2 && intervals[d] > 0 && (aktd = dd.quot - vacc) > 0; i++) { if (d != edges[i]) continue; intervals[d] -= 1; saved += aktd; vacc += 1; } while (intervals[d] > 0 && (aktd = d - 2 * vacc) > 0) { vacc += min(aktd, 2); saved += max(aktd - 1, 1); intervals[d] -= 1; } } return n - saved; } int main() { ios_base::sync_with_stdio(0); int t; cin >> t; for (int k = 0; k < t; k++) { cout << solve() << endl; } return 0; } |