CF1665B Array Cloning Technique

给定一个长度为 $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$。

对于每个测试用例，输出一个整数，表示最少需要多少次操作，才能得到一个所有元素都相等的副本。

在第一个测试用例中，数组的所有元素已经相等，因此答案为 $0$。 在第二个测试用例中，可以先克隆一次原数组，此时有两个相同的数组： $[0\ 1\ 3\ 3\ 7\ 0]$ 和 $[0\ 1\ 3\ 3\ 7\ 0]$ 然后可以交换元素，使得所有的 $0$ 都在一个数组中： $[0\ \underline{0}\ \underline{0}\ 3\ 7\ 0]$ 和 $[\underline{1}\ 1\ 3\ 3\ 7\ \underline{3}]$ 接着克隆第一个数组： $[0\ 0\ 0\ 3\ 7\ 0]$，$[0\ 0\ 0\ 3\ 7\ 0]$ 和 $[1\ 1\ 3\ 3\ 7\ 3]$ 再交换前两个副本中的元素： $[0\ 0\ 0\ \underline{0}\ \underline{0}\ 0]$，$[\underline{3}\ \underline{7}\ 0\ 3\ 7\ 0]$ 和 $[1\ 1\ 3\ 3\ 7\ 3]$ 最终，我们得到了一个所有元素都相等的副本，总共进行了 $6$ 次操作。 可以证明，不可能用更少的操作完成。 由 ChatGPT 4.1 翻译