#A0010. 移动棋子
移动棋子
题目描述
有一条被分成 个格子的带子,这些格子从左到右编号为 到 。每个格子要么有一个棋子,要么是空的。
你可以进行如下操作任意次(也可以不进行):选择一个棋子,将它移动到它左侧最近的空格子上。你可以选择任意一个棋子,只要它左边至少有一个空格子。移动后,原来棋子所在的格子变为空格。
你的目标是通过若干次操作,使所有棋子连成一块,中间没有空格。你需要求出最少需要多少次操作。
输入格式
第一行包含一个整数 (),表示测试用例的数量。
每个测试用例包含两行:
- 第一行包含一个整数 (),表示格子的数量;
- 第二行包含 个整数 (), 表示第 个格子为空, 表示第 个格子有一个棋子。
输入保证每个测试用例至少有一个格子有棋子。

输出格式
对于每个测试用例,输出一个整数,表示将所有棋子移动成一块且中间没有空格所需的最少操作次数。
输入输出样例 #1
输入 #1
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
1
0
0
2
3
说明/提示
在第一个样例中,你可以对第 个格子的棋子进行操作。它左边最近的空格是第 个格子,于是将其移动到那里。此时所有棋子连成一块。
在第二个样例中,所有棋子已经连成一块。第三个样例同理。
由 ChatGPT 4.1 翻译