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
#include <iostream>
#include <queue>

using namespace std;

int main() {
  int t, n, healthyCitiesSeries, savedCities, daysPassed;
  string citiesList;
  bool begin;
  priority_queue<int> healthyCitiesSegments;
  cin >> t;

  for (int i = 0; i < t; i++) {
    cin >> n >> citiesList;
    begin = true, healthyCitiesSeries = 0, daysPassed = 0, savedCities = 1;
    healthyCitiesSegments = priority_queue<int>();
    for (int j = 0; j < n; j++) {
      if (citiesList[j] == '1') {
        if (begin) {
          healthyCitiesSegments.push(2 * healthyCitiesSeries);
          begin = false;
        } else {
          healthyCitiesSegments.push(healthyCitiesSeries);
          healthyCitiesSegments.push(healthyCitiesSeries);
        }
        healthyCitiesSeries = 0;
      } else {
        healthyCitiesSeries++;
      }
    }
    healthyCitiesSegments.push(2 * healthyCitiesSeries);
    while (!healthyCitiesSegments.empty() &&
           healthyCitiesSegments.top() > daysPassed * 2) {
      savedCities += healthyCitiesSegments.top() - daysPassed * 2;
      healthyCitiesSegments.pop();
      daysPassed++;
    }
    cout << n -  savedCities / 2 <<endl;
  }
  return 0;
}