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
#include <cstdio>
#include <cstdlib>
#include <cassert>

#include <algorithm>

int double_holes[100 * 1000];
int single_holes[2];

void do_test() {
    int n;
    int base_sick_cities = 0;
    assert(1 == scanf("%d", &n));

    int last_pos = -1;

    int n_single = 0;
    int n_double = 0;

    for (int i = 0; i < n; i++) {
        int c = getchar();
        if (c == '1') {
            base_sick_cities++;
            if (last_pos == -1 && i > 0) {
                single_holes[n_single++] = i;
            } else if (last_pos + 1 != i) {
                double_holes[n_double++] = i - last_pos - 1;
            }
            last_pos = i;
        } else if (c != '0') {
            i--; // Skip whitespace
        }
    }

    if (last_pos != -1 && last_pos + 1 != n) {
        single_holes[n_single++] = n - last_pos - 1;
    }

    if (base_sick_cities == 0) {
        puts("0");
        return;
    }

    std::sort(single_holes, single_holes + n_single);
    std::sort(double_holes, double_holes + n_double);

    int saved_cities = 0;
    int elapsed = 0;

    auto process_single_hole = [&] {
        const int remaining_now = std::max(0, single_holes[--n_single] - elapsed);
        if (remaining_now > 0) {
            saved_cities += remaining_now;
            elapsed++;
        }
    };

    auto process_double_hole = [&] {
        int remaining_now = std::max(0, double_holes[--n_double] - 2 * elapsed);
        if (remaining_now > 2) {
            saved_cities += remaining_now - 1;
            elapsed += 2;
        } else if (remaining_now > 0) {
            saved_cities++;
            elapsed++;
        }
    };

    while (n_double > 0 && n_single > 0) {
        const int worth_single = std::max(0, single_holes[n_single - 1] - elapsed);
        const int worth_double = std::max(0, double_holes[n_double - 1] - 2 * elapsed);

        if (2 * worth_single >= worth_double) {
            process_single_hole();
        } else {
            process_double_hole();
        }
    }

    while (n_single > 0) {
        process_single_hole();
    }

    while (n_double > 0) {
        process_double_hole();
    }

    printf("%d\n", n - saved_cities);
}

int main() {
    int t;
    assert(1 == scanf("%d", &t));

    while (t --> 0) {
        do_test();
    }

    return 0;
}