AT_abc254_h [ABC254Ex] Multiply or Divide by 2 题解

打篇题解巩固一下。

题意

给你两个集合 \(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;
}