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
#include <stdio.h>
#include <queue>
#include <utility>
using namespace std;
char buff[1000000+7];
int main(void) {
	size_t TC; scanf("%lu", &TC);
	while (TC--) {
		size_t n;
		scanf("%lu", &n);
		// char *buff = new char[n+1];
		scanf("%s", buff);
		priority_queue<pair<size_t, bool>> longest; // pair: longest intervals, is_extreme?

		size_t result = 0;
		for (size_t i=0; i<n; ++i)
			if (buff[i] == '1')
				++result;
		size_t i = 0;
		for (; i < n && buff[i] == '0'; ++i);
		if (i == n) { printf("0\n"); continue; }
		longest.push(make_pair(i*2, true));

		size_t length = 0;
		for (; i < n; ++i) {
			if (buff[i] == '1') {
				if (length != 0) {
					longest.push(make_pair(length, false));
					// longest.push(length);
					// longest.push(length);
				}
				length = 0;
			} else {
				++length;
			}
		}
		if (length != 0)
			longest.push(make_pair(length*2, true));

		size_t next_length = 0;
		while (!longest.empty()) {
			auto p = longest.top();
			longest.pop();

			if (p.second) {
				result += min(next_length, p.first/2);
				++next_length;
			} else {
				// result += min(next_length*2 + 1, p.first-1);
				result += min(next_length, p.first/2 + (p.first%2));
				result += min(next_length+1, p.first/2);
				next_length += 2;

				// if (next_length+1 >= p.first) {
				// 	result += min(next_length, p.first);
				// 	next_length += 1;
				// } else {
				// }
			}
		}

		printf("%lu\n", result);
	}
	return 0;
}