311025: CF1923A. Moving Chips
Description
There is a ribbon divided into $n$ cells, numbered from $1$ to $n$ from left to right. Each cell either contains a chip or is free.
You can perform the following operation any number of times (possibly zero): choose a chip and move it to the closest free cell to the left. You can choose any chip that you want, provided that there is at least one free cell to the left of it. When you move the chip, the cell where it was before the operation becomes free.
Your goal is to move the chips in such a way that they form a single block, without any free cells between them. What is the minimum number of operations you have to perform?
InputThe first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.
Each test case consists of two lines:
- the first line contains one integer $n$ ($2 \le n \le 50$) — the number of cells;
- the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1$); $a_i = 0$ means that the $i$-th cell is free; $a_i = 1$ means that the $i$-th cell contains a chip.
Additional constraint on the input: in each test case, at least one cell contains a chip.
OutputFor each test case, print one integer — the minimum number of operations you have to perform so that all chips form a single block without any free cells between them.
ExampleInput5 8 0 1 1 1 0 1 1 0 6 0 1 0 0 0 0 6 1 1 1 1 1 1 5 1 0 1 0 1 9 0 1 1 0 0 0 1 1 0Output
1 0 0 2 3Note
In the first example, you can perform the operation on the chip in the $7$-th cell. The closest free cell to the left is the $5$-th cell, so it moves there. After that, all chips form a single block.
In the second example, all chips are already in a single block. Same for the third example.
Output
题目描述了一个棋盘，有n个单元格，从左到右编号为1到n。每个单元格要么包含一个筹码，要么为空。你可以执行以下操作任意次数（可能为零次）：选择一个筹码并将其移动到左侧最近的空单元格。你可以选择任何筹码，只要它左侧至少有一个空单元格。当移动筹码时，筹码原先所在的单元格变为空。目标是移动筹码，使它们形成一个单一区块，没有空单元格在它们之间。需要输出的是达到目标所需的最小操作次数。
输入数据格式：
第一行包含一个整数t（1≤t≤1000）——测试用例的数量。
每个测试用例包含两行：
- 第一行包含一个整数n（2≤n≤50）——单元格的数量；
- 第二行包含n个整数a1, a2, …, an（0≤ai≤1）；ai=0表示第i个单元格是空的，ai=1表示第i个单元格包含一个筹码。
输出数据格式：
对于每个测试用例，输出一个整数——需要进行的最小操作次数，以便所有筹码形成没有空单元格的单一区块。
例：
输入：
5
8
0 1 1 1 0 1 1 0
6
0 1 0 0 0 0
6
1 1 1 1 1 1
5
1 0 1 0 1
9
0 1 1 0 0 0 1 1 0
输出：
1
0
0
2
3
注意：
- 在第一个例子中，可以对第7个单元格中的筹码执行操作。左侧最近的空单元格是第5个，所以筹码移动到那里。之后，所有筹码形成一个单一区块。
- 在第二个和第三个例子中，所有筹码已经形成单一区块。题目大意： 题目描述了一个棋盘，有n个单元格，从左到右编号为1到n。每个单元格要么包含一个筹码，要么为空。你可以执行以下操作任意次数（可能为零次）：选择一个筹码并将其移动到左侧最近的空单元格。你可以选择任何筹码，只要它左侧至少有一个空单元格。当移动筹码时，筹码原先所在的单元格变为空。目标是移动筹码，使它们形成一个单一区块，没有空单元格在它们之间。需要输出的是达到目标所需的最小操作次数。 输入数据格式： 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。 每个测试用例包含两行： - 第一行包含一个整数n（2≤n≤50）——单元格的数量； - 第二行包含n个整数a1, a2, …, an（0≤ai≤1）；ai=0表示第i个单元格是空的，ai=1表示第i个单元格包含一个筹码。 输出数据格式： 对于每个测试用例，输出一个整数——需要进行的最小操作次数，以便所有筹码形成没有空单元格的单一区块。 例： 输入： 5 8 0 1 1 1 0 1 1 0 6 0 1 0 0 0 0 6 1 1 1 1 1 1 5 1 0 1 0 1 9 0 1 1 0 0 0 1 1 0 输出： 1 0 0 2 3 注意： - 在第一个例子中，可以对第7个单元格中的筹码执行操作。左侧最近的空单元格是第5个，所以筹码移动到那里。之后，所有筹码形成一个单一区块。 - 在第二个和第三个例子中，所有筹码已经形成单一区块。