打篇题解巩固一下。
题意
给你两个集合 \(A\) 和 \(B\)，对于任意 \(A\) 集合中的元素，我们可以进行 \(2\) 种操作：\(a_i\gets \left\lfloor\frac{a_i}{2}\right\rfloor\) 或 \(a_i\gets 2\times a_i\)。问最少要多少次才能使 \(A\) 和 \(B\) 中的元素相等。
分析
首先我们可以令 \(a=\max_A\)，\(b=\max_B\)。
- 若 \(a=b\) 则可以消去 \(2\) 数。之后继续寻找 \(A\) 和 \(B\) 中最大的元素。
- 若 \(a<b\) 则说明 \(b\) 大于 \(A\) 中全部的元素。\(a\gets 2\times a\) 等价于 \(b\gets \frac{b}{2}\)，当且仅当 \(b\) 为 \(2\) 的倍数。
- 若 \(a>b\) 则说明 \(a\) 大于 \(B\) 中全部的元素。使 \(a\gets \left\lfloor\frac{a}{2}\right\rfloor\)。
最后输出操作次数即可。
注意
要使 \(a_i\gets \left\lfloor\frac{a_i}{2}\right\rfloor\) 等于 \(a_i\gets 2\times a_i\)，就必须使 \(a\) 为 \(2\) 的倍数。如果不是，则无解 。
代码实现
这里用优先队列维护 \(A\) 和 \(B\) 的最大值。
#include <bits/stdc++.h>
using namespace std;
int n, ans;
priority_queue<int> A, B;//构建优先队列
int main() {
cin>>n;
//存储
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
A.push(a);
}
for (int i = 0; i < n; ++i) {
int b;
cin >> b;
B.push(b);
}
while (!A.empty()) {
if (A.top() < B.top()) {
if (B.top() % 2) {//判断是否无解
printf("-1");
return 0;
} else {
int t = B.top();
B.pop();
B.push(t / 2);
}
} else if (A.top() > B.top()) {
int temp = A.top();
A.pop();
A.push(temp / 2);
} else {
A.pop();
B.pop();
continue;
}
ans += 1;//计数
}
cout << ans << endl;
return 0;
}