A16472. Seats
编程题
普及-
知识点
题目描述
Cordell 管理着 Piova 市立音乐学校的一排 $n$ 个座位，学校严格禁止学生彼此相邻就坐。
给定一个二进制字符串 $s$，其中 $s_i = \mathtt{1}$ 表示第 $i$ 个座位已经有学生就坐，而 $s_i = \mathtt{0}$ 表示当前空闲。保证当前不会有两个相邻的座位都已被占用。Cordell 需要继续安排更多学生，直到无法再安排任何学生，但她希望用尽可能少的新学生就达到这种“无法再安排”状态。
你的任务是计算，当无法再安排任何新学生时，排中最少的总就座学生人数。
$^\text{∗}$ 二进制字符串指每个字符都是 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。
给定一个二进制字符串 $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$。
每组测试数据的第一行包含一个整数 $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
1 1 2 3 5
说明/提示
在第一个测试用例中，$n=1$，初始时教室是空的。由于还可以安排学生，Cordell 必须安排一名学生坐在第 1 号座位。此时就座人数最少为 $1$。
在第三个测试用例中，Cordell 可以安排两名学生分别坐在第 1 和第 4 个座位。可以证明，无论如何安排一名学生，都无法让排无法继续安排新生，因此答案为 $2$。
在第四个测试用例中，无法再安排新学生，所以 Cordell 不需要额外安排，他总共安排的学生人数是 $3$。
在第三个测试用例中，Cordell 可以安排两名学生分别坐在第 1 和第 4 个座位。可以证明，无论如何安排一名学生，都无法让排无法继续安排新生，因此答案为 $2$。
在第四个测试用例中，无法再安排新学生，所以 Cordell 不需要额外安排，他总共安排的学生人数是 $3$。