← 返回题目列表

Codeforces · 1665/B

B. 阵列克隆技术

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。最初,给定数组只有一份副本。

您可以执行两种类型的操作:

1. 选择任意阵列并克隆它。之后,就会有一份所选数组的副本。
2. 交换任意位置上任意两个副本(可能在同一个副本中)的两个元素。

您需要找到获得所有元素都相等的副本所需的最少操作数。

输入

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

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

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

输出

对于每个测试用例,输出一个整数 - 创建至少一个所有元素都相等的副本所需的最少操作数。

示例

输入 #1

6
1
1789
6
0 1 3 3 7 0
2
-1000000000 1000000000
4
4 3 2 1
5
2 5 7 6 3
7
1 1 1 1 1 1 1

输出 #1

0
6
2
5
7
0

注意

在第一个测试用例中,数组中的所有元素都已经相等,这就是为什么答案是 $$$0$$$。

在第二个测试用例中,可以创建给定数组的副本。之后将有两个相同的数组:

$$$[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$$$ 和 $$$[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$$$

之后,我们可以以一种方式交换元素,使所有零都在一个数组中:

$$$[ \ 0 \ \下划线{0} \ \下划线{0} \ 3 \ 7 \ 0 \ ]$$$ 和 $$$[ \ \下划线{1} \ 1 \ 3 \ 3 \ 7 \ \下划线{3} \ ]$$$

现在让我们创建第一个数组的副本:

$$$[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$$$、$$$[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$$$ 和 $$$[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$$$

让我们交换前两个副本中的元素:

$$$[ \ 0 \ 0 \ 0 \ \下划线{0} \ \下划线{0} \ 0 \ ]$$$、$$$[ \ \下划线{3} \ \下划线{7} \ 0 \ 3 \ 7 \ 0 \ ]$$$ 和 $$$[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$$$。

最后,我们制作了一个所有元素都相等的副本,并进行了 $$$6$$$ 操作。

可以证明,操作次数不少就够了。