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

int main(void) {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T;
  std::cin >> T;
  for (int t = 0; t < T; t++) {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    std::vector<int> groups[2];
    for (int i = 0; i < n; i++) {
      if (s[i] == '0') {
        int start = i;
        int end = start;
        for (i = start + 1; i < n && s[i] == '0'; i++) {
          end = i;
        }
        int borders = ((start > 0 && s[start-1] == '1') ? 1 : 0) + ((end + 1 < n && s[end+1] == '1') ? 1 : 0);
        if (borders != 0) {
          groups[borders-1].push_back(end - start + 1);
        }
      }
    }
    if (groups[0].size() + groups[1].size() == 0) {
      std::cout << 0 << std::endl;
      continue;
    }
    std::sort(groups[0].begin(), groups[0].end(), std::greater<int>());
    std::sort(groups[1].begin(), groups[1].end(), std::greater<int>());
    int i = 0, j = 0, turns = 0, score = 0, gain0, gain1;
    do {
      gain0 = i < groups[0].size() ? groups[0][i] : 0;
      gain1 = j < groups[1].size() ? groups[1][j] - 1 : 0;
      gain0 -= turns;
      gain1 -= turns * 2;
      gain0 = std::max(0, gain0);
      gain1 = std::max(0, gain1);
      if (gain1 >= gain0) {
        score += gain1;
        j++;
        turns += 2;
      } else {
        score += gain0;
        i++;
        turns++;
      }
      //std::cerr << score << ' ' << turns << ' ';
    } while (gain0 > 0 || gain1 > 0);
    std::cout << (n - score) << std::endl;
  }
  return 0;
}