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
#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

struct block {
	block(int _l, int _vacc) : length(_l), vaccines_needed(_vacc) {}
	int length;
	int vaccines_needed;

	friend bool operator< (const block& l, const block& r) {
		return (l.length - l.vaccines_needed) < (r.length - r.vaccines_needed);
	}
};

int main() {
	std::ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		int saved_population = 0;
		bool is_initial = true;
		int current_healthy_block_length = 0;

		list<block> blocks;
		for (int i = 0; i < n; i++) {
			char town;
			cin >> skipws >> town;
			if (town == '1') { // sick
				if (current_healthy_block_length > 0) {
					cerr << "saving block " << current_healthy_block_length << ',' << is_initial << endl;
					blocks.push_back(block(current_healthy_block_length, is_initial ? 1 : 2));
				}
				is_initial = false;
				current_healthy_block_length = 0;
			} else {
				current_healthy_block_length++;
			}
		}
		if (is_initial) { // wow, no sick ones!
			cout << 0 << endl;
			continue;
		}
		if (current_healthy_block_length > 0)
			blocks.push_back(block(current_healthy_block_length, 1));
		while (!blocks.empty()) {
			auto max_it = max_element(blocks.begin(), blocks.end());
			cerr << "loaded block [" << max_it->length << ',' << max_it->vaccines_needed << "]\n";
			if (max_it->length <= 0) // no more healthy cities
				break;
			if (max_it->vaccines_needed == 1) { // close block
				cerr << "saved " << max_it->length << " cities\n";
				saved_population += max_it->length;
				blocks.erase(max_it);
			} else {
				max_it->vaccines_needed--;
			}
			for_each(blocks.begin(), blocks.end(), [] (block& f) { f.length -= f.vaccines_needed; });
		}
		cout << n - saved_population << endl;
	}
	return 0;
}