给一个长度为 \(n\) 的数组 \(a\) 。开始只有一份所给 \(a\) 的副本。你可以做以下两种操作：
- 选择任意一个副本并且克隆它，然后将会多出一个克隆副本。
- 交换两个元素，他们属于任意两个副本（可能是同一个）。
需要判断最小操作数，使有一个副本的所有元素相同。
观察一：只需要在开始的副本上让所有元素相同，不相同的元素丢到其他副本。
观察二：每次执行复制后，初始副本的相同元素是倍增的。
于是统计初始副本相同元素最多的个数 \(cur\) 。每次副本执行复制和交换后将有 \(cnt = cnt + cur + 1\) ，\(cur = cur + cur\) 。直到 \(cur \geq n\) ，\(cnt - (cur - n)\) 即答案。
- 若只有 \(cur - n > 0\) 才能满足 \(cur - n \geq 0\) ，则 \(cur - n\) 为多出的交换数。
view
#include <bits/stdc++.h>
void solve() {
int n = 0; std::cin >> n;
std::vector<int> a(n+1);
std::map<int, int> px;
int cur = 0; for (int i = 1; i <= n; i++) std::cin >> a[i], px[a[i]]++, cur = std::max(cur, px[a[i]]);
int cnt = 0; while (cur < n) {
cnt += cur + 1;
cur += cur;
}
std::cout << cnt - (cur - n) << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}