首页 > 试题广场 >

数组同构

[编程题]数组同构
  • 热度指数：631 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}定义变换函数：
\hspace{23pt}\bullet\,将一个正整数 x 用其二进制表示中 1 的个数替换，记作 g(x)（即 \operatorname{popcount}）；
\hspace{15pt}给定两个长度均为 n 的正整数数组 A 和 B；
\hspace{15pt}你可以对 A 或 B 中的任意元素反复执行以下操作，每次操作计数 1：
\hspace{23pt}\bullet\,将该元素 x 替换为 g(x)；
\hspace{15pt}当且仅当存在置换 \pi，使得对所有 1\leqq i\leqq n 都有 A_i = B_{\pi(i)}，也就是两个数组都排序后完全相同，我们称 A 与 B 同构。请计算使 A 与 B 同构所需的最少操作次数。
\hspace{15pt}可以证明题目一定有解。

输入描述:
\hspace{15pt}第一行输入一个整数 t\ \left(1\leqq t\leqq 10^{4}\right)，表示测试用例数； 
\hspace{15pt}每个测试用例输入格式如下： 
\hspace{23pt}\bullet\,第一行输入一个整数 n\ \left(1\leqq n\leqq 2\times 10^{5}\right)； 
\hspace{23pt}\bullet\,第二行输入 n 个整数 A_1, A_2, \dots, A_n\ \left(1\leqq A_i\leqq10^{18}\right)； 
\hspace{23pt}\bullet\,第三行输入 n 个整数 B_1, B_2, \dots, B_n\ \left(1\leqq B_i\leqq10^{18}\right)； 
\hspace{15pt}保证所有测试用例中 \sum n \leqq 2\times 10^{5}。


输出描述:
\hspace{15pt}对于每个测试用例，输出一行整数——使 A 与 B 同构的最少操作次数。
示例1

输入

2
3
4 1 2
2 2 1
3
7 3 5
3 3 5

输出

2
1

说明

\hspace{23pt}\bullet\,初始时，A=\{4,1,2\},\ B=\{2,2,1\}； 
\hspace{23pt}\bullet\,对 A 中元素 4 执行一次变换，得到 g(4)=1，此时 A=\{1,1,2\}； 
\hspace{23pt}\bullet\,对 B 中一个元素 2 执行一次变换，得到 g(2)=1，此时 B=\{1,2,1\}； 
\hspace{23pt}\bullet\,此时两数组的元素可以一一匹配，故最少操作数为 2。 

\hspace{15pt}在第二个测试用例中：仅需将 A 中的 7 变换为 g(7)=3，得到 A=\{3,3,5\}，与 B 相同，操作数为 1。
算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-08-28 00:32:05
题目链接 数组同构 题目描述 定义一个变换函数 ，其值为正整数 的二进制表示中 的个数。例如，。 给定两个长度均为 的正整数数组 和 。我们可以对 或 中的任意元素 执行变换操作，将其变为 ，每次操作计为 次。这个过程可以反复进行。 当两个数组排序后能够完全相同时，我们称它们是“同构 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 牛客253536348号
发表于 2025-08-27 12:53:49
#include <iostream> #include <queue> #include <vector> using namespace std; int popcount(long x) { int res = 0; while (x) { 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 找工作的葡萄
发表于 2025-08-29 22:21:00
#include <iostream> #include <queue> using namespace std; int GFunction(long x) { // 默认 x >= 1 int res = 0; while (x) { 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 位运算 堆
难度：
1条回答 185浏览

热门推荐

相关试题

数组同构

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号