526互联

Codeforces Round 781 (Div. 2) B. Array Cloning Technique

发布时间 2023-09-13 20:41:51作者: zsxuan

给一个长度为 \(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;
}