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
/* 2021
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>
#include <queue>

int tests;
int cities;
char status[131072];

int solve();

int main(void)
{
    scanf("%d", &tests);
    for(int t = 0; t < tests; ++t)
    {
        scanf("%d %s", &cities, status);
        printf("%d\n", solve());
    }

    return 0;
}

int solve()
{
    int c = 0;
    while(c < cities && status[c] == '0')
        ++c;

    std::priority_queue<int> side;
    std::priority_queue<int> both;
    if(c)
        side.push(c);

    int current = 0;
    for(; c < cities; ++c)
    {
        if(status[c] == '0')
            ++current;
        else if(current)
        {
            both.push(current);
            current = 0;
        }
    }

    if(current)
        side.push(current);

    int result = 0;
    for(int day = 0; side.size() || both.size(); ++day)
    {
        while(side.size() && side.top() <= day)
        {
            // printf("Day %d: S.out(%d)\n", day, side.top());
            side.pop();
        }

        while(both.size() && both.top() <= 2 * day)
        {
            // printf("Day %d: B.out(%d)\n", day, both.top());
            both.pop();
        }

        if(side.size() && (!both.size() || side.top() - day >= both.top() - 2 * day - 2))
        {
            // printf("Day %d: fully vacc %d\n", day, side.top() - day);
            result += side.top() - day;
            side.pop();
        }

        else if(both.size())
        {
            ++result;
            // printf("Day %d: partially vacc %d\n", day, both.top() - 2 * day);
            side.push(both.top() - day - 1);
            both.pop();
        }
    }

    return cities - result;
}