A15040 | Array Cloning Technique
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given an array $a$ of $n$ integers. Initially there is only one copy of the given array.
You can do operations of two types:
1. Choose any array and clone it. After that there is one more copy of the chosen array.
2. Swap two elements from any two copies (maybe in the same copy) on any positions.
You need to find the minimal number of operations needed to obtain a copy where all elements are equal.
You can do operations of two types:
1. Choose any array and clone it. After that there is one more copy of the chosen array.
2. Swap two elements from any two copies (maybe in the same copy) on any positions.
You need to find the minimal number of operations needed to obtain a copy where all elements are equal.
输入格式
The input consists of multiple test cases. The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer $n$ ( $1 \le n \le 10^5$ ) — the length of the array $a$ .
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $-10^9 \le a_i \le 10^9$ ) — the elements of the array $a$ .
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$ .
The first line of each test case contains a single integer $n$ ( $1 \le n \le 10^5$ ) — the length of the array $a$ .
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $-10^9 \le a_i \le 10^9$ ) — the elements of the array $a$ .
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$ .
输出格式
For each test case output a single integer — the minimal number of operations needed to create at least one copy where all elements are equal.
输入输出样例
输入 #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
In the first test case all elements in the array are already equal, that's why the answer is $0$ .
In the second test case it is possible to create a copy of the given array. After that there will be two identical arrays:
$[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$ and $[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$
After that we can swap elements in a way so all zeroes are in one array:
$[ \ 0 \ \underline{0} \ \underline{0} \ 3 \ 7 \ 0 \ ]$ and $[ \ \underline{1} \ 1 \ 3 \ 3 \ 7 \ \underline{3} \ ]$
Now let's create a copy of the first array:
$[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$ , $[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$ and $[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$
Let's swap elements in the first two copies:
$[ \ 0 \ 0 \ 0 \ \underline{0} \ \underline{0} \ 0 \ ]$ , $[ \ \underline{3} \ \underline{7} \ 0 \ 3 \ 7 \ 0 \ ]$ and $[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$ .
Finally, we made a copy where all elements are equal and made $6$ operations.
It can be proven that no fewer operations are enough.
In the second test case it is possible to create a copy of the given array. After that there will be two identical arrays:
$[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$ and $[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$
After that we can swap elements in a way so all zeroes are in one array:
$[ \ 0 \ \underline{0} \ \underline{0} \ 3 \ 7 \ 0 \ ]$ and $[ \ \underline{1} \ 1 \ 3 \ 3 \ 7 \ \underline{3} \ ]$
Now let's create a copy of the first array:
$[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$ , $[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$ and $[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$
Let's swap elements in the first two copies:
$[ \ 0 \ 0 \ 0 \ \underline{0} \ \underline{0} \ 0 \ ]$ , $[ \ \underline{3} \ \underline{7} \ 0 \ 3 \ 7 \ 0 \ ]$ and $[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$ .
Finally, we made a copy where all elements are equal and made $6$ operations.
It can be proven that no fewer operations are enough.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted