← 返回题目列表

Codeforces · 1433/B

B. 又一个书架

中文机器翻译题面 查看原题

有一个书架,可容纳 $$$n$$$ 本书。如果书架上的第 $$$i$$$ 位置有书,则 $$$a_i = 1$$$,否则 $$$a_i = 0$$$。保证书架上至少有一本书。

在一次移动中,您可以选择一些连续的段 $$$[l; r]$$$ 由书籍组成(即,对于从 $$$l$$$ 到 $$$r$$$ 的每个 $$$i$$$,条件 $$$a_i = 1$$$ 成立)并且:

- 将其向右移动 $$$1$$$:将所有 $$$l \le i \le r$$$ 的索引 $$$i$$$ 处的书移动到 $$$i + 1$$$。仅当 $$$r+1 \le n$$$ 并且位置 $$$r+1$$$ 处没有书时才可以进行此移动。
- 将其向左移动 $$$1$$$:将所有 $$$l \le i \le r$$$ 的索引 $$$i$$$ 处的书移动到 $$$i-1$$$。仅当 $$$l-1 \ge 1$$$ 并且位置 $$$l-1$$$ 处没有书时才可以进行此移动。

您的任务是找到将书架上的所有书籍收集为连续(连续)段(即没有任何间隙的段)所需的最少移动次数。

例如,对于 $$$a = [0, 0, 1, 0, 1]$$$ 书籍之间有间隙(当 $$$a_3 = 1$$$ 且 $$$a_5 = 1$$$ 时,$$$a_4 = 0$$$),对于 $$$a = [1, 1, 0]$$$ 书籍之间没有间隙,对于 $$$a = [0, 0,0]$$$ 书之间也没有间隙。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 书架上的位置数。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$),其中如果该位置有一本书,则 $$$a_i$$$ 为 $$$1$$$,否则为 $$$0$$$。保证书架上至少有一本书。

输出

对于每个测试用例,打印一个整数:将书架上的所有书籍收集为连续(连续)段(即没有间隙的段)所需的最小移动次数。

示例

输入 #1

5
7
0 0 1 0 1 0 1
3
1 0 0
5
1 1 0 0 1
6
1 0 0 0 0 1
5
1 1 0 1 1

输出 #1

2
0
2
4
1

注意

在示例的第一个测试用例中,您可以移动段 $$$[3; 3]$$$ 向右,段 $$$[4; 5]$$$ 向右。在所有移动之后,书籍形成连续段 $$$[5; 7]$$$。所以答案是$$$2$$$。

在示例的第二个测试用例中,您无需执行任何操作,书架上的所有书籍都已形成连续的段。

在示例的第三个测试用例中,您可以移动段 $$$[5; 5]$$$ 向左,然后是段 $$$[4; 4]$$$ 再次向左。在所有移动之后,书籍形成连续段 $$$[1; 3]$$$。所以答案是$$$2$$$。

在示例的第四个测试用例中,您可以移动段$$$[1; 1]$$$ 向右,段$$$[2; 2]$$$ 向右,段 $$$[6; 6]$$$ 向左,然后是段 $$$[5; 5]$$$ 向左。在所有移动之后,书籍形成连续段 $$$[3; 4]$$$。所以答案是$$$4$$$。

在示例的第五个测试用例中,您可以移动段 $$$[1; 2]$$$ 向右。在所有移动之后,书籍形成连续段 $$$[2; 5]$$$。所以答案是$$$1$$$。