前言
本文是对 DennyQi 题解思想的补充做法。
题目翻译
$n$ 个数 $a_i$，每次可以选择 $a_i\gets a_i\times 2$ 或者 $a_i\gets \lfloor\frac{a_i}{2}\rfloor$。
问几次操作后 $a_i$ 全部一样。
$1\leq n\leq 10^5$，$1\leq a_i\leq 10^5$。
题目思路
考虑把这个操作对应到二进制上，那么就是删除一位和添加一个 $0$，其实就是位运算中的右移 $1$ 位和左移 $1$ 位。
你不会对这些数进行很多次移位，这样子不如每个数都少移动几位。因此最后这些数的二进制长度也就是 $\log_2 10^5$ 级别左右的，实现的时候可以取到 $18$ 防止一些不必要的判断。
每一个数最多移动 $\log$ 位就会变成 $0$，由于刚才说的，操作之后也是 $\log$ 级别，因此每右移一位都可以左移 $\log$ 位，一个数至多有 $\log^2$ 种可达状态。
但是状态有重复，考虑去重。本身复杂度已经是 $\mathcal O(n \log^2 V)$ 了，去重使用单次 $\mathcal O(\log n)$ 复杂度的数据结构可能过不去，我们需要设计一种单次 $\mathcal O(1)$ 得到重复状态中步数最小的。
那么我们考虑记录 $mn_i,lst_i$ 表示，我们上一次往答案里面扔的数，是 $a_{lst_i}$ 造成的，且对于所有的 $lst_j=lst_i$，他们最小扔进去的是 $mn_i$。
那么如果我们再往里面扔一个 $lst_j=lst_i$ 的方案，直接对于这个 $mn_i$ 判断要不要更新答案和 $mn_i$。如果扔进去的不是 $lst_i$ 造成的贡献，我们直接把 $lst_i,mn_i$ 等重构成目前的信息即可。
说这么多，其实本质就是记录上次修改是不是自己造成的，如果是自己造成的就把修改的数取最优。
实现的时候还要记录每个状态被不同的数贡献了几次，只有恰好贡献 $n$ 次才可能让所有数都变成它。
完整代码
复杂度 $\mathcal O(n\log^2 n)$。
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
const int LOG = 18;
int n;
int cnt[1 << 20];
int tot[1 << 20];
int lst[1 << 20];
int mn[1 << 20];
int ans = 1e9;
void add(int x, int y, int z) // cnt[y] += x id = z
{
if (lst[y] == z)
{
cnt[y] -= mn[y];
chkmn(mn[y], x);
cnt[y] += mn[y];
}
else
mn[y] = x, lst[y] = z, cnt[y] += x, tot[y]++;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
for (int j = 0; j <= LOG; j++)
{
int y = x;
int tmp = 0;
for (int k = 1; k <= j; k++)
y >>= 1, tmp++;
add(tmp, y, i);
for (int k = 1; k <= LOG && (y << 1) < (1 << 20); k++)
y <<= 1, tmp++, add(tmp, y, i);
}
}
for (int i = 0; i < 1 << 20; i++)
{
if (tot[i] == n)
chkmn(ans, cnt[i]);
}
cout << ans << endl;
return 0;
}