解题思路

题目给定两个长度为 $n$ 的正整数数组 $a,b$ 。

一次操作中，可以在数组 $a$ 中选出若干个当前数值相同的元素，并把它们同时乘 $2$ 。目标是用最少操作次数，让 $a$ 和 $b$ 的元素多重集合完全相同，顺序无关；如果无法实现，输出 $-1$ 。

一个数在不断乘 $2$ 的过程中，它的“奇数部分”永远不会改变。

P4797.第3题-倍增对齐

1000ms

Difficulty: 5

所属公司 : 美团

算法与标签>贪心算法

在神秘的魔法工坊中，小美有两个魔法阵列 $a$ 和 $b$ ，长度均为 $n$ 。在一次操作中，她可以在 $a$ 中选择若干个值相同的元素，并将它们的值同时翻倍一次（即乘以 $2$ ）。

小美希望通过若干次操作，使阵列 $a$ 的元素多重集合与阵列 $b$ 完全一致（不要求顺序，只关心元素及其出现次数）。

请计算将 $a$ 变换为 $b$ 的元素多重集合所需的最小操作次数；如果无法实现，则输出 $-1$ 。

第一行输入一个整数 $T(1≤T≤10^5)$ ，表示测试数据组数。
每组测试数据描述如下：
- 第一行输入一个整数 $n(1≤n≤10^5)$ ，表示数组长度。
- 第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$ ，表示初始数组 $a$ 。
- 第三行输入 $n$ 个整数 $b_1,b_2,…,b_n(1≤b_i≤10^9)$ ，表示目标数组 $b$ 。

保证所有测试用例中 $n$ 的总和不超过 $5×10^5$ 。

对于每组测试数据，输出一行一个整数，表示将 $a$ 转换为与 $b$ 元素多重集合相同所需的最小操作次数；如果无法实现，则输出 $-1$ 。

输入

输出

2
2
-1

说明

样例一:{ $1,2,3$ } $\rightarrow$ { $2,4,3$ },先将 $1\rightarrow 2$ , 再将 $2\rightarrow 4$ ,共 $2$ 步。

样例二:{ $1,1,2,2$ } $\rightarrow$ { $4,2,2,1$ }。可对一个 $1$ 倍化一次对一个 $2$ 倍化一次，最少 $2$ 步。

样例三: $9$ 不是 $5×2^k$ 的形式，故无解，输出 $-1$ 。

输入

预期输出（选填）