Codeforces 558C Amr and Chemistry：枚舉可達值統計最小操作步數

題目大意

n 個數 a_i，每步可將某數 ×2 或 ÷2（整除）。求使所有數相等的最少總操作數。

核心思想

對每個數 x，枚舉其所有可達值及對應最小步數：
- 不斷除 2 直到 0，記錄路徑上的值及步數。
- 對路徑上的每個值（特別是奇數），可先除 2 再乘 2 到達 x-1（如 7→3→6），步數 +2，繼續乘 2 擴展。
統計全局 cnt[v]（能到達 v 的數個數）與 sum[v]（總步數）。
答案為滿足 cnt[v]==n 的最小 sum[v]。

枚舉邏輯細節

#include 
using namespace std;
const int LIM = 200005;
int cnt[LIM], sum[LIM];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    while (cin >> n) {
        fill(cnt, cnt+LIM, 0);
        fill(sum, sum+LIM, 0);
        for (int i=0, x; i> x;
            // 枚舉 x 所有可達值
            auto up = [&](int y, int s) {
                for (; y < LIM; y <<= 1, ++s) {
                    cnt[y]++; sum[y] += s;
                }
            };
            up(x, 0);
            int step = 1, y = x;
            while (y) {
                if (y > 1 && (y & 1)) {
                    int z = (y >> 1) << 1; // y-1
                    up(z, step + 1);
                }
                y >>= 1;
                cnt[y]++; sum[y] += step;
                up(y, step);
                ++step;
            }
        }
        int ans = INT_MAX;
        for (int v = 1; v < LIM; ++v)
            if (cnt[v] == n) ans = min(ans, sum[v]);
        cout << ans << '\n';
    }
    return 0;
}

複雜度

每個數枚舉可達值 O(log MAX) 個，每個值向上擴展 O(log MAX) 步。總體 O(n log² MAX)，MAX=2e5，n≤1e5，極快。