P16857 [GKS 2021 #F] Trash Bins

在你居住的城市 Kickstartland 中，有一条特别长的街道，街上有 $N$ 栋房子。这条街道的长度为 $N$，$N$ 栋房子均匀分布在街上，即第 $1$ 栋房子位于位置 $1$，第 $2$ 栋房子位于位置 $2$，依此类推。任意两栋房子 $i$ 和 $j$ 之间的距离为 $|i - j|$，其中 $|x|$ 表示 $x$ 的绝对值。 其中一些房子的门前有垃圾桶。这意味着这些房子的主人倒垃圾时无需行走。然而，对于门前没有垃圾桶的房子的主人，他们必须走向某个门前有垃圾桶的房子（要么向左，要么向右）。 为了节省时间，每个房子的主人总是将垃圾带到离自己房子最近的垃圾桶处。如果两个垃圾桶距离该房子一样近，则主人可以走向其中任意一个。 给定房子的数量 $N$，以及哪些房子门前有垃圾桶的描述，请计算出每个房子的主人倒垃圾所需行走的距离之和。你可以假设至少有一栋房子门前有垃圾桶。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由两行组成。 每个测试用例的第一行包含一个整数 $N$，表示街道上房子的数量。 每个测试用例的第二行包含一个长度为 $N$ 的字符串 $S$，表示哪些房子门前有垃圾桶。如果字符串 $S$ 的第 $i$ 个字符等于 $1$，则表示第 $i$ 栋房子门前有垃圾桶；否则，如果等于 $0$，则表示第 $i$ 栋房子门前没有垃圾桶。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是每个房子的主人倒垃圾所需行走的距离之和。

对于第 $1$ 个测试用例，每个房子门前都有垃圾桶，因此没有房主需要行走倒垃圾。 对于第 $2$ 个测试用例，第 $1$ 栋和第 $4$ 栋房子的主人门前有垃圾桶，因此他们无需行走。第 $2$ 栋房子的主人将走向第 $1$ 栋房子，距离为 $1$。第 $3$、$5$ 和 $6$ 栋房子的主人将走向第 $4$ 栋房子，距离分别为 $1$、$1$ 和 $2$。 ### 限制条件 $1 \le T \le 100$。 $S$ 的长度等于 $N$。 $S$ 的每个字符为 $0$ 或 $1$。 $S$ 中至少有一个字符 $1$。 **测试集 1** $1 \le N \le 100$。 **测试集 2** $1 \le N \le 5 \times 10^5$。 翻译由 DeepSeek V4 Pro 完成