美团 · 堆 · 算法编程题
美团 堆 n ≤ 200000 时限 3 秒 / 256 MB

题目描述

定义变换函数：
将一个正整数 x 用其二进制表示中 1 的个数替换，记作 g(x) （即 popcount ）；
给定两个长度均为 n 的正整数数组 A 和 B ；
你可以对 A 或 B 中的任意元素反复执行以下操作，每次操作计数 1 ：
将该元素 x 替换为 g(x) ；
当且仅当存在置换 ，使得对所有 1≤ i≤ n 都有 A_i = B_(i) ，也就是两个数组都排序后完全相同，我们称 A 与 B 同构。请计算使 A 与 B 同构所需的最少操作次数。
可以证明题目一定有解。

输入输出

输入描述
第一行输入一个整数 t(1≤ t≤ 10^4) ，表示测试用例数；
每个测试用例输入格式如下：
第一行输入一个整数 n(1≤ n≤ 2× 10^5) ；
第二行输入 n 个整数 A_1, A_2, ..., A_n(1≤ A_i≤10^18) ；
第三行输入 n 个整数 B_1, B_2, ..., B_n(1≤ B_i≤10^18) ；
保证所有测试用例中 Σ n ≤ 2× 10^5 。
输出描述
对于每个测试用例，输出一行整数——使 A 与 B 同构的最少操作次数。

样例共 1 组

样例 1 · 初始时， A=\4,1,2,B=\2,2,1 ； 对 A 中元素 4 执行一次变换，得到 g(4)=1 ，此时 A=\1,1,2 ； 对 B 中一个元素 2 执行一次变换，得到 g(2)=1 ，此时 B=\1,2,1 ； 此时两数组的元素可以一一匹配，故最少操作数为 2 。 在第二个测试用例中：仅需将 A 中的 7 变换为 g(7)=3 ，得到 A=\3,3,5 ，与 B 相同，操作数为 1 。
输入
2
3
4 1 2
2 2 1
3
7 3 5
3 3 5
输出
2
1

算法解析依据充分

考点：堆 · 贪心

数据规模 n ≤ 200000 ｜ 限制 3 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 200000，t ≤ 1e4
  • 元素值域：A_i ≤ 1e18，B_i ≤ 1e18（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：堆

用堆在 O(log n) 内取极值，求 TopK 与动态中位数。

思路框架（堆 通法 · 非本题专属）

  1. 求最大 K 个：维护大小 K 的小根堆，超了就把堆顶弹出。
  2. 动态中位数：用「对顶堆」——小的一半放在大根堆，大的一半放在小根堆，两个堆顶就是中位数。
  3. 移动窗口中的中位数需要配合「延迟删除」处理过期元素。

实现要点：Python 的 heapq 是小根堆，要大根堆就存负数。

复杂度：时间 O(n log k) / O(n log n) ｜ 空间 O(k)

该范式的通法易错点

  • 求第 K 大时堆类型选反（小根堆还是大根堆）。
  • 窗口滑出元素时忘记从堆里清理或标记过期。

对照本题

  • 数据规模 n ≤ 200000，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 元素值域最大到 1e18 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 2 / 3 / 4 1 2 / 2 2 1 / 3 / 7 3 5 / 3 3 5 → 输出 2 / 1

初始时， A=\4,1,2,B=\2,2,1 ；

对 A 中元素 4 执行一次变换，得到 g(4)=1 ，此时 A=\1,1,2 ；

对 B 中一个元素 2 执行一次变换，得到 g(2)=1 ，此时 B=\1,2,1 ；

此时两数组的元素可以一一匹配，故最少操作数为 2 。

在第二个测试用例中：仅需将 A 中的 7 变换为 g(7)=3 ，得到 A=\3,3,5 ，与 B 相同，操作数为 1 。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-美团-全栈岗-第二批笔试；2025年秋招-美团-前端&移动端-第二批笔试；2025年秋招-美团-运维&安全岗-第二批笔试 等。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解