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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <deque>

using namespace std;

struct Section {
  int size;
  int multiply;
};

int main()
{
  int n, l;
  string s;
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> l >> s;
    int days = 0;
    int sum = 0;
    auto b = s.find('0');
    auto e = s.find('1', b);
    deque<Section> ss;
    if (b == 0 && e == string::npos) {
      cout << 0 << endl;
      continue;
    } else if (b == string::npos) {
      cout << l << endl;
      continue;
    } else {
      while (b != string::npos) {
        if (b == 0) {
          ss.emplace_back(Section{static_cast<int>(e), 1});
        } else if (e == string::npos) {
          ss.emplace_back(Section{static_cast<int>(l - b), 1});
//          int tmp = l - b - days;
//          if (tmp > 0)
//            sum += tmp;
          break;
        } else { // in the middle
          ss.emplace_back(Section{static_cast<int>(e - b), 2});
//          int tmp = e - b - 2*days;
//          if(tmp == 1 || tmp == 2) {
//            sum++;
//            days++;
//          }
//          if (tmp > 2) {
//            sum += (tmp - 1);
//            days += 2;
//          }
        }
        b = s.find('0', e);
        if (b == string::npos)
          break;
        e = s.find('1', b);
      }
    }

    while (!ss.empty()) {
      //find the best
      int the_best_index = 0;
      float the_best_value = 0.0;
      for(int i = 0; i < ss.size(); i++) {
        auto tmp = 1.0 * ss[i].size / ss[i].multiply;
        if (tmp > the_best_value) {
          the_best_index = i;
          the_best_value = tmp;
        }
      }
      ss[the_best_index].multiply--;
      ss[the_best_index].size--;
      sum++;

      for(auto &s : ss) {
        s.size -= s.multiply;
      }

      for(auto it = ss.begin(); it < ss.end(); ) {
        if(it->size<=0) {
          it = ss.erase(it);
        } else if (it->multiply == 0) {
          sum += it->size;
          it = ss.erase(it);
        } else {
          it++;
        }
      }
    }

    cout << l-sum << endl;
  }

  return 0;
}