守护神兽的修炼计划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)$。

参考代码

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;
}