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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct pp {
    int idx;
    int val;
};

bool myfunction (pp i, pp j) { return i.val < j.val; }

int main() {
    int MAX = 100001, k;
    cin >> k;
    for (int ik = 0; ik < k; ik++) {
        vector<int> one, two;
        int n, d[MAX] = {0,}, saved = 0, l = 0, di = 0, k;
        char b[MAX];
        cin >> n >> b;
        for (int i = 0; i < n; i++) {
            if (b[i] == '1') {
                d[di++] = l;
                l = 0;
            } 
            else {
                l++;
            }
        }
        d[di] = l;
        /*
        cout << "d :";
        for (int i = 0; i <= di; i++) cout << d[i] << " ";
        cout << endl;
        */
        if (d[0] > d[di]) {
            one = {di, 0};
        }
        else {
            one = {0, di};
        }
        if (di == 0) one.pop_back();
        vector<pp> v;
        for (int i = 1; i < di; i++) {
            pp p = {i, d[i]};
            v.push_back(p);
        }
        sort(v.begin(), v.end(), myfunction);
        for (int i = 0; i < v.size(); i++) {
            two.push_back(v[i].idx);
        }
        for (int t = 0; t < n; t++) {
            /*
            cout << "one: ";
            for (int i = 0; i < one.size(); i++) cout << one[i] << " ";
            cout << endl;
            cout << "two: ";
            for (int i = 0; i < two.size(); i++) cout << two[i] << " ";
            cout << endl;
            */
            int oned = 0;
            if (!one.empty()) oned = d[one.back()];
            int twod = 0;
            if (!two.empty()) twod = d[two.back()];
            if (2 * oned > twod) {
                saved += max(0, oned - t);
                if (!one.empty()) one.pop_back();
            }
            else {
                saved += max(0, twod - (2*t + 1));
                if (!two.empty()) two.pop_back();
                if (twod == 2*t + 1) saved++;            
                else t++;
            }
            //cout << "saved: " << saved << endl;
            if (one.empty() && two.empty()) break;
        }
        cout << n - saved << endl;
    }
    return 0;
}