← 返回题目列表

Codeforces · 1993/B

B. 奇偶校验和和

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

给定一个包含 $$$n$$$ 正整数的数组 $$$a$$$。

在一次操作中,您可以选择任意一对索引 $$$(i, j)$$$,使得 $$$a_i$$$ 和 $$$a_j$$$ 具有不同的奇偶性,然后用它们的总和替换较小的索引。更正式地说:

- 如果 $$$a_i < a_j$$$,则将 $$$a_i$$$ 替换为 $$$a_i + a_j$$$;
- 否则,将 $$$a_j$$$ 替换为 $$$a_i + a_j$$$。

求使数组的所有元素具有相同奇偶校验所需的最少操作数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 所需的最少操作数。

示例

输入 #1

7
5
1 3 5 7 9
4
4 4 4 4
3
2 3 4
4
3 2 2 8
6
4 3 6 1 2 1
6
3 6 1 2 1 2
5
999999996 999999997 999999998 999999999 1000000000

输出 #1

0
0
2
4
3
3
3

注意

在第一个测试用例中,所有整数已经具有相同的奇偶校验。因此,不需要进行任何操作。

在第三个测试用例中,我们可以执行两个操作 $$$(1, 2)$$$ 和 $$$(1, 3)$$$。数组 $$$a$$$ 变换如下: $$$a = [\color{red}2, \color{red}3, 4] \longrightarrow [\color{red}5, 3, \color{red}4] \longrightarrow [5, 3, 9]$$$。

在第四个测试用例中,最佳操作序列的示例是 $$$(1, 2)$$$、$$$(1, 3)$$$、$$$(1, 4)$$$ 和 $$$(1, 4)$$$。数组 $$$a$$$ 变换如下: $$$a = [\color{red}3, \color{red}2, 2, 8] \longrightarrow [\color{red}3, 5, \color{red}2, 8] \longrightarrow [\color{red}3, 5, 5, \color{red}8] \longrightarrow [\color{red}{11}, 5, 5, \color{red}8] \longrightarrow [11, 5, 5, 19]$$$。