Codeforces Amr and Chemistry：數學與暴力構造最小操作數

問題描述

給定 n 個數 a_i。每次操作可將某數乘 2 或除以 2（向下取整，即右移）。求使所有數相等的最小總操作次數。

核心觀察

任意數 x 可表示為 x = s * 2^k（s 為奇數）。通過乘除 2，x 可到達的所有值為 s' * 2^p，其中 s' 是 s 不斷除以 2 得到的奇數序列（含 s 本身），p ≥ 0，且值 ≤ 100000（題目隱含上限）。每個數可達值數量極少（最多幾百個）。

算法流程

1. 對每個 a_i，枚舉其所有可達值 v 及對應操作數 cost。
2. 維護兩個全局數組 cnt[v]（能到達 v 的數的個數）和 sumCost[v]（到達 v 的總操作數）。
3. 最後遍歷 v = 1..100000，若 cnt[v] == n，用 sumCost[v] 更新答案最小值。

枚舉可達值的代碼邏輯

// 以 abc 為原始值
int t = abc, cnt = 1, cnt1 = 0;
abc <<= 1;
while (abc <= 100000) { // 向上乘2
    vol[abc]++; ans[abc] += cnt;
    cnt++; abc <<= 1;
}
cnt = 0;
while (t % 2 == 0) { // 向下除2直到奇數
    vol[t]++; ans[t] += cnt;
    cnt++; cnt1++; t >>= 1;
}
vol[t]++; ans[t] += cnt; // 奇數本身
t >>= 1; cnt1++;
while (t != 0) { // 奇數繼續除2（變為更小奇數），每步再向上乘2
    int u = t, cnt2 = cnt1;
    while (u <= 100000) {
        vol[u]++; ans[u] += cnt2;
        cnt2++; u <<= 1;
    }
    if (t % 2 == 0) {
        while (t % 2 == 0) { t >>= 1; cnt1++; vol[t]++; ans[t] += cnt1; }
    }
    t >>= 1; cnt1++;
}

複雜度

每個數可達值 ≤ 200 左右，總操作 O(n * 200)，n ≤ 1e5 極快。空間 O(100000)。