题解 | #游游的除2操作#

给大家一种好理解的做法吧

简化题意：每个数都可以进行若干次除2的操作，最终需要使所有数相同，输出最少的操作次数

我们可以发现，对一个数进行 i 次除2，等效于在将其二进制右移 i 位，而一个 1e9范围内 的数通过除2能得到的数，最多只有29个，我可以轻松的维护出每个数 x 右移 i 位得到的数 y

那我们回到题目，最终要求所有数相同，也就是说所有的数都需要有一个相同的最终状态 Y ，所以我们可以在之前维护 y 的时候将其的权值加一，表示能到达 y 这个状态的数的个数，顺便维护一下当前的 x 到达 y 这个状态需要的步数，也就是 i ，对于每个 y ，我们维护一个 pair<int,int> ，first 表示能到达 y 这个状态的数的个数，second 表示每个数到达 y 这个状态需要的步数，很明显，如果 first == n ，那么答案就是 second

然后回到题目，要找到最小的 second ，对于所有 first == n 的 y ，一定是 y 最大的那个 second 最小，所以我们可以用一个 map<int,pair<int,int>,greater<int>> 来维护这个信息，方便在后面直接使用 auto [k,v] : mp 来从大到小遍历

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int __t = 1, n, x;
void solve() {
    cin >> n;
    map<int, pair<int, int>, greater<int>> mp;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        for (int i = 0; x >> i; i++) {
            mp[x >> i].first++;
            mp[x >> i].second += i;
        }
    }
    for (auto [k, v] : mp) {
        if (v.first == n) {
            cout << v.second << '\n';
            return;
        }
    }
    return;
}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    // cin >> __t;
    while (__t--)
        solve();
    return 0;
}