← 返回题目列表

Codeforces · 1834/A

A. 单位阵列

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

给定一个长度为 $$$n$$$ 的数组 $$$a$$$,其元素等于 $$$-1$$$ 和 $$$1$$$。如果同时满足以下条件,我们称数组 $$$a$$$ 好:

- $$$a_1 + a_2 + \ldots + a_n \ge 0$$$;
- $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n = 1$$$。

在一次操作中,您可以选择数组 $$$a_i$$$ 中的任意元素并将其值更改为相反的值。换句话说,如果 $$$a_i = -1$$$,则可以将值分配给 $$$a_i := 1$$$,如果 $$$a_i = 1$$$,则可以将值分配给 $$$a_i := -1$$$。

确定使数组 $$$a$$$ 正常所需执行的最少操作数。可以证明这总是可能的。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i = \pm 1$$$) — 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,输出一个整数 - 使 $$$a$$$ 数组正常运行所需的最少操作数。

示例

输入 #1

7
4
-1 -1 1 -1
5
-1 -1 -1 1 1
4
-1 1 -1 1
3
-1 -1 -1
5
1 1 1 1 1
1
-1
2
-1 -1

输出 #1

1
1
0
3
0
1
2

注意

在第一个测试用例中,我们可以分配值 $$$a_1 := 1$$$。那么 $$$a_1 + a_2 + a_3 + a_4 = 1 + (-1) + 1 + (-1) = 0 \ge 0$$$ 和 $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 = 1 \cdot (-1) \cdot 1 \cdot (-1) = 1$$$。因此,我们执行了$$$1$$$操作。

在第二个测试用例中,我们可以分配 $$$a_1 := 1$$$。然后 $$$a_1 + a_2 + a_3 + a_4 + a_5 = 1 + (-1) + (-1) + 1 + 1 = 1 \ge 0$$$ 和 $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 = 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot 1 = 1$$$。因此,我们执行了$$$1$$$操作。

在第三个测试用例中, $$$a_1 + a_2 + a_3 + a_4 = (-1) + 1 + (-1) + 1 = 0 \ge 0$$$ 和 $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 = (-1) \cdot 1 \cdot (-1) \cdot 1 = 1$$$。因此,所有条件都已满足,无需任何操作。

在第四个测试用例中,我们可以分配值 $$$a_1 := 1, a_2 := 1, a_3 := 1$$$。然后 $$$a_1 + a_2 + a_3 = 1 + 1 + 1 = 3 \ge 0$$$ 和 $$$a_1 \cdot a_2 \cdot a_3 = 1 \cdot 1 \cdot 1 = 1$$$。因此,我们执行了 $$$3$$$ 操作。