A16472 | $Seats$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Cordell 管理着 Piova 市立音乐学校的一排 $n$ 个座位，学校严格禁止学生彼此相邻就坐。 给定一个二进制字符串 $s$，其中 $s_i = \mathtt{1}$ 表示第 $i$ 个座位已经有学生就坐，而 $s_i = \mathtt{0}$ 表示当前空闲。保证当前不会有两个相邻的座位都已被占用。Cordell 需要继续安排更多学生，直到无法再安排任何学生，但她希望用尽可能少的新学生就达到这种“无法再安排”状态。 你的任务是计算，当无法再安排任何新学生时，排中最少的总就座学生人数。 $^\text{∗}$ 二进制字符串指每个字符都是 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

每个测试点包含多组测试数据。第一行为测试用例个数 $t$（$1 \le t \le 10^4$）。每组测试数据描述如下。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示这一排有 $n$ 个座位。 第二行包含一个长度为 $n$ 的二进制字符串 $s$（$s_i \in \{\mathtt{0}, \mathtt{1}\}$）。保证字符串中不会有两个相邻的 $\mathtt{1}$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示达到无法再就座时，排中最少的总就坐学生人数。

输入 #1

5
1
0
3
000
5
00000
6
100101
13
0000100001000

输出 #1

C++ 编辑器

输入

输出