[ABC254Ex] Multiply or Divide by 2

题意：

给定大小为 $ n $ 的集合 $ A $ 和 $ B $，你可以对集合 $ A $ 中的元素 $ a_i $ 进行两种操作，分别为 $ a_i \leftarrow \lfloor \dfrac{a_i}{2} \rfloor $，和 $ a_i \leftarrow a_i \times 2 $。你需要操作集合 $ A $ 直至集合 $ A, B $ 完全相同。求最小操作次数，若无解输出 -1。

分析：

考虑每次对 \(A,B\) 的最大值进行操作，记 \(A\) 的最大值为 \(mx_A\)，\(B\) 的最大值为 \(mx_B\)。

• \(mx_A=mx_B\) 直接消掉即可。
• \(mx_A>mx_B\)：直接 $mx_A \leftarrow \lfloor \dfrac{mx_A}{2} \rfloor $。
• \(mx_A<mx_B\)： 此时只能用操作 \(2\)，但这样就会破坏性质，只用对 $mx_B \leftarrow \dfrac{mx_B}{2} $ 即可，需要注意的是如果 \(mx_B\) 为奇数，就说明 \(A\) 集合内的元素一直乘 \(2\) 都不可能与 \(mx_B\) 相等，即无解。

这样保证了 \(A,B\) 集合内在操作后都为递减。总操作次数最多为 \(\log V\)。

维护这个过程可以使用优先队列。

总时间复杂度 \(O(n \log n \log V)\)。

代码：

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int read() {
	char ch = getchar(); int x = 0, f = 1;
	while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
void write(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar('0' + x % 10);
}
int n, ans;
int a[N], b[N];
priority_queue<int>Q1, Q2;
signed main() {
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read(), Q1.push(a[i]);
    for(int i = 1; i <= n; i++) b[i] = read(), Q2.push(b[i]);
    while(!Q1.empty()) {
    	int x = Q1.top(), y = Q2.top();
    	ans++;
    	if(x == y) Q1.pop(), Q2.pop();
    	else if(x > y) Q1.pop(), Q1.push(x / 2);
    	else if(x < y) {
    		if(y % 2 == 1) {
    			write(-1);
    			return 0;
			}
			Q2.pop();
			Q2.push(y / 2);
		}
	}
	write(ans - n); 
	return 0;
}