题解 | 数组同构

#include <iostream>
#include <queue>
using namespace std;
int GFunction(long x) { // 默认 x >= 1
    int res = 0;
    while (x) {
        res += x & 1;
        x >>= 1;
    }
    return res;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        priority_queue<long> A;
        priority_queue<long> B;
        for (int i = 0; i < n; ++i) {
            long a;
            cin >> a;
            A.push(a);
        }
        for (int i = 0; i < n; ++i) {
            long b;
            cin >> b;
            B.push(b);
        }
        int operationCount = 0;
        while (!A.empty() && !B.empty()) {
            long Aptr = A.top(), Bptr = B.top();
            if (Aptr == Bptr) {
                A.pop();
                B.pop();
            } else if (Aptr > Bptr) {
                Aptr = GFunction(Aptr);
                operationCount++;
                A.pop();
                A.push(Aptr);
            }else {
                Bptr = GFunction(Bptr);
                operationCount++;
                B.pop();
                B.push(Bptr);
            }
        }
        cout << operationCount << endl;
    }
}
// 64 位输出请用 printf("%lld")

感谢账号“牛客253536348号”的兄台分享的题解，我来记录一下我在这道题上踩的坑。

共识：“不难想到……排序后，每次再从两组数据尾部找更大的值x，丢进G(x)中”

一、打一开始，咱就钻了个最细的牛角尖！！！

用vector存储数据，sort（）两次，用指针记录结尾最大值max, max' = G(max)后，在另一个vector中查找 max'标记删除(这里即使使用lower_bound查找第一个大于等于的值，也需要额外时间复杂度 O（logn ），况且为了标记删除，而修改该值以后，lower_bound()二分查找由于数组不再有序，结果变得不再可控, 不能再头铁重排吧), 那么好~这么烂的思路，我不超时谁超时？教训如下：

1、容器/数据结构使用不熟练：

（1）需要数据有序，且每次只访问两组数据的最大值

（2）max' = G(max)后，不需要在另一组数据中查找再删除对应的max'，而是反向操作将新的max'插回原来数据组，供后续继续比较

（3）具体选择过程：

c++有序容器包括：set（值唯一）、map、multiset、multimap、priority_queue(容器适配器、模拟堆、非全局有序)

能存重复值，且查找最大值复杂度O（1）的两个候选人：multiset和priority_queue,

multiset（底层红黑树），由于每次插入要保证全局有序，所以多出几步平衡、旋转步骤，实际执行时间应该会比priority_queue（底层二叉堆）的更长一些

所以我们选priority_queue(默认大顶堆): 每次只取两组数据的最大值

2、数据范围：不要用int!!! 除非 #include <cstdint> // uint64

两组数据的范围是 1 <= ai <= 10^18（这里豆包建议我用 long long 可存储最大值≈9.22 * 10 ^18， 说long 在32位编译系统下用4字节存储，可存储的最大值≈2* 10 ^9， 但代码里编译通过了，我承认我有赌的成分哈哈……）