题解 | 数组同构

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int popcount(long x) {
    int res = 0;
    while (x) {
        res += x & 1;  
        x >>= 1;
    }
    return res;
}

int main() {
    int t;
    cin >> t;

    for (int test_case = 0; test_case < t; test_case++) {
        int n;
        cin >> n;

        priority_queue<long> a_queue;
        priority_queue<long> b_queue;

        for (int i = 0; i < n; i++) {
            long a;
            cin >> a;
            a_queue.push(a);
        }

        for (int i = 0; i < n; i++) {
            long b;
            cin >> b;
            b_queue.push(b);
        }

        int counter = 0;

        while (!a_queue.empty()) {
            long a_max = a_queue.top();
            long b_max = b_queue.top();

            if (a_max == b_max) {
                a_queue.pop();
                b_queue.pop();
            } else if (a_max > b_max) {
                a_queue.pop();
                long new_val = popcount(a_max);
                a_queue.push(new_val);
                counter++;
            } else {
                b_queue.pop();
                long new_val = popcount(b_max);
                b_queue.push(new_val);
                counter++;
            }

        }

        cout << counter << endl; 
    }
    return 0;
}

本题核心思路是注意到，a数组的最大值，设为A，b数组的最大值设为B，AB之中更大的一方至少要进行一次popcount()运算。若A与B相等，则AB直接配对，不进行运算为最优（数学归纳法可证）