守护神兽的修炼计划II tag 数论，枚举，图论？ 题意简述 给定 $n$ 个数 $a_i$，每次可以选择一个数 $a_i$，令 $a_i \leftarrow a_i \times 2$，或者令 $a_i \leftarrow \lfloor \frac{a_i}{2} \rfloor$。求令所有数相等的最小操作次数。 题解思路 分析题意，我们考虑将所有的数变成目标数 $P$，$P$ 应该形如：$P = X \times 2^n$，其中 $X$ 是所有数的公共可达点。公共可达点指的是，所有数都可以通过若干次除以2的操作变成 $X$。我们这里只考虑通过除以2的操作变成 $X$，因为乘以2的操作形成的公共可达点可以通过枚举 $P = X \times 2^n$ 中的 $n$ 来得到，他们的 $X$ 本质相同，而只有除以二存在向下取整的操作，可能会出现新的 $X$。可以使用map容器来记录所有数的可达点权值，每次出现一个数就+1，最后权值为n的数就是所有数的公共可达点。最后，我们枚举所有的 $X$ 的 $2$ 的整数次幂的倍数，作为目标数，然后依次计算即可。 时间复杂度分析：我们枚举所有的数，不断除2直到为 $0$，得到每个数的可达点，时间复杂度是 $O(\log n)$。同时，需要注意的，公共可达点的数的数量不会超过 $\log \log n$ 个(估计的，无证明)。随后枚举所有的公共可达点（即 $X$）的 $2$ 的整数次幂的倍数，时间复杂度是 $O(\log n)$。随后每次计算每个数变成目标数 $P$ 的操作次数，时间复杂度是 $O(n \log n)$。所以总时间复杂度是 $O(n \log^2 n \log \log n)$。约等于 $O(n \log^2 n)$。 参考代码 ```cpp signed main() { IOS; int n; cin >> n; vector<int> a(n + 1); map<int, int> mp; // 记录可达点的权值 for(int i = 1; i <= n; i ++) { cin >> a[i]; int t = a[i]; int c = 0; while(t) // 枚举所有可达点 { mp[t]++; t >>= 1; } } // 计算 u 以 base 为可达点，变成 x 的操作次数 auto calc = [&](int u,int x, int base) -> int { int t = 0; while(u > base) { // 如果 base 是 u 的一个可达点，那么 u 可以直接除2变成 x if(u == x) return t; t ++; u /= 2; } // 否则先变成 base，再变成 x while(base < x) { t ++; base *= 2; } return t; }; i64 ans = 1e18; for(auto [i, c] : mp) { // 只有权值为 n 的可达点才会被枚举 if(c < n) continue; i64 t = 0; // 枚举他的所有2的整数次幂的倍数 for(int k = i; k <= 1e5; k *= 2) { t = 0; for(int j = 1; j <= n; j ++) { t += calc(a[j], k, i); } ans = min(ans, t); } } cout << ans << '\n'; return 0; } ```