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 <vector>
#include <algorithm>

int main()
{
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{
		std::vector<int> health_intervals;
		int edge_interval1, edge_interval2;
		edge_interval1 = -1;
		int n;
		scanf("%d\n", &n);
		health_intervals.reserve(n);
		int counter = 0;
		for (int i = 0; i < n; i ++)
		{
			char state;
			scanf("%c", &state);
			if (state == '0')
				counter++;
			else
			{
				if (edge_interval1 == -1)
					edge_interval1 = counter;
				else if (counter > 0)
					health_intervals.push_back(counter);
				counter = 0;
			}
		}
		edge_interval2 = counter;
		std::sort(health_intervals.begin(), health_intervals.end(), std::greater<int>());
		int number_of_cities_saved = 0;
		int max_interval_index = 0;
		for (int i = 0; i < n; i++)
		{
			if ((max_interval_index >= health_intervals.size()) || ((edge_interval2 - i > 0 || edge_interval1 - i > 0 ) && (edge_interval1 - i + 2 >= health_intervals[max_interval_index] - 2 * i || edge_interval2 - i + 2 >= health_intervals[max_interval_index] - 2 * i)))
			{
				if (edge_interval1 > edge_interval2)
				{
					number_of_cities_saved += std::max(edge_interval1 - i, 0);
					edge_interval1 = 0;
				}
				else
				{
					number_of_cities_saved += std::max(edge_interval2 - i, 0);
					edge_interval2 = 0;
				}
			}
			else
			{
				number_of_cities_saved += std::max(health_intervals[max_interval_index] - 2 * i, 0);
				if (health_intervals[max_interval_index] - 2 * i > 1)
				{
					number_of_cities_saved--;
					if (health_intervals[max_interval_index] - 2 * i > 2)
						i++;
				}
				max_interval_index++;
			}
		}
		printf("%d\n", n - number_of_cities_saved);
	}
}