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
#include <bits/stdc++.h>
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    string s;
    cin >> n >> s;
    vector<pair<int, int>> value_cost;
    int st = 0;
    int en = -1;
    for (int i = 0; i < n; i++) {
      if (s[i] == '0') {
        en = i;
      } else { // s[i] == '1'
        bool is_beg = st == 0;
        if (is_beg) {
          value_cost.push_back({2 * (en - st + 1), 1});
        } else {
          value_cost.push_back({en - st + 1, 0});
        }
        st = i + 1;
      }
    }
    if (s.back() == '0') {
      value_cost.push_back({2 * (n - 1 - st + 1), 1});
    }
    int day = 0;
    int saved = 0;
    sort(value_cost.rbegin(), value_cost.rend());

    for (auto v : value_cost) {
      if (v.second == 1) {
        if (v.first / 2 - day > 0) {
          saved += (v.first / 2 - day);
          day++;
        }
      } else { // v.second == 2
        if (v.first - 2 * day > 0) {
          saved++;
          day++;
          if (v.first - 2 * day > 0) {
            saved += (v.first - 2 * day);
            day++;
          }
        }
      }
    }
    cout << n - saved << endl;
  }
}