题目链接

数组同构

题目描述

定义一个变换函数 ，其值为正整数 的二进制表示中 的个数。例如，。

给定两个长度均为 的正整数数组 和 。我们可以对 或 中的任意元素 执行变换操作，将其变为 ，每次操作计为 次。这个过程可以反复进行。

当两个数组排序后能够完全相同时，我们称它们是“同构”的。请计算使数组 和 同构所需的最少操作次数。

解题思路

本题要求计算将两个数组 和 变为同构所需的最少操作次数。变换操作 的值是 的二进制表示中 1 的个数。

关键性质在于，对于任何大于 1 的整数 ， 总是小于 。这意味着变换是单向的，只能将大数变为小数。这个性质是贪心策略的基础。

既然无法将小数变为大数，那么当我们比较两个数组中当前未匹配的最大数时，如果它们不相等，那么其中较大的那个数就必须被变换，因为它不可能由一个更小的数变来。

这个思路可以用**优先队列（大顶堆）**非常优雅地实现：

  1. 创建两个大顶堆，pq_A 和 pq_B，分别装入数组 和 的所有元素。
  2. 循环比较两个堆的堆顶元素（即当前两个数组中未匹配的最大值）：
    • 如果 pq_A.top() == pq_B.top()，说明当前两个数组的最大值可以匹配。我们将它们同时从堆中弹出。
    • 如果 pq_A.top() > pq_B.top()，说明 中的最大值更大。根据我们的贪心策略，这个数必须被变换。我们将其弹出，计算它的 值，然后将新值重新推入 pq_A。同时，操作数加一。
    • 如果 pq_B.top() > pq_A.top()，则对 pq_B 执行对称的操作。
  3. 不断重复此过程，直到两个堆都变为空。此时累计的操作数即为最少操作次数。

这种方法在每一步都处理当前的最大元素，做出了局部最优决策（变换那个不得不变的大数），从而保证了全局解的最优性。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

#ifdef _WIN32
#include <intrin.h>
#define __builtin_popcountll __popcnt64
#endif

using namespace std;

void solve() {
    int n;
    cin >> n;
    priority_queue<long long> q1, q2;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        q1.push(x);
    }
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        q2.push(x);
    }

    long long ans = 0;
    while (!q1.empty()) {
        long long top1 = q1.top();
        long long top2 = q2.top();
        if (top1 == top2) {
            q1.pop();
            q2.pop();
        } else if (top1 > top2) {
            ans++;
            q1.pop();
            q1.push(__builtin_popcountll(top1));
        } else { // top2 > top1
            ans++;
            q2.pop();
            q2.push(__builtin_popcountll(top2));
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.PriorityQueue;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        PriorityQueue<Long> q1 = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            q1.add(sc.nextLong());
        }
        
        PriorityQueue<Long> q2 = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            q2.add(sc.nextLong());
        }

        long ans = 0;
        while (!q1.isEmpty()) {
            long top1 = q1.peek();
            long top2 = q2.peek();

            if (top1 == top2) {
                q1.poll();
                q2.poll();
            } else if (top1 > top2) {
                ans++;
                q1.poll();
                q1.add((long)Long.bitCount(top1));
            } else { // top2 > top1
                ans++;
                q2.poll();
                q2.add((long)Long.bitCount(top2));
            }
        }
        System.out.println(ans);
    }
}

import heapq

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    # Python的heapq是小顶堆，所以我们存入负数来模拟大顶堆
    pq1 = [-x for x in a]
    pq2 = [-x for x in b]
    heapq.heapify(pq1)
    heapq.heapify(pq2)

    ans = 0
    while pq1:
        top1 = -pq1[0]
        top2 = -pq2[0]

        if top1 == top2:
            heapq.heappop(pq1)
            heapq.heappop(pq2)
        elif top1 > top2:
            ans += 1
            heapq.heappop(pq1)
            heapq.heappush(pq1, -bin(top1).count('1'))
        else: # top2 > top1
            ans += 1
            heapq.heappop(pq2)
            heapq.heappush(pq2, -bin(top2).count('1'))

    print(ans)

t = int(input())
for _ in range(t):
    solve()

算法及复杂度

  • 算法：贪心、优先队列 (堆)
  • 时间复杂度：对于单个测试用例，设数组长度为 。
    • 将所有元素插入两个优先队列的时间为 。
    • while 循环中的每次操作（弹出或推入）代价为 。一个数 经过少数几次变换就会变得很小，因此总的变换次数 不会太多。循环的总迭代次数为 。
    • 总时间复杂度为 ，考虑到 的增长远慢于 ，复杂度可近似视为 。
  • 空间复杂度：，用于存储两个优先队列。