F. Equate Multisets（贪心）

Codeforces Round #805 (Div. 3)

Problem

给出两个长度都为n的数组a和b。每次可以对b中任意一个数进行两个操作中的一个：（1）乘二（2）向下取整除二。
操作顺序不限制，次数不限制，问：经过一些操作后，b能否与a相同。

Solution

1. 首先可以先把a中的数进行除二，直到变成奇数。
   理由：如果b数组可以变成a数组，那么，同样可以变成改变后的数组。如果不能变成改变后数组，就表示无解。
2. 此时a数组中都是奇数，那么操作一就无效了。只剩下操作二。
3. 由于b中的数现在只能变小，所以，应该从b中最大数开始不断进行操作二。
   如果最后变成0都无法与a中某个数相同，那么无解。

Code

const int N = 2e5 + 5, M = 1e6 + 7;
int a[N], b[N];
map<int, int> mp;

int main()
{
	IOS;
	int T; cin >> T;
	while (T--)
	{
		mp.clear();
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		for (int i = 1; i <= n; i++) cin >> b[i];

		for (int i = 1; i <= n; i++)
		{
			while (a[i] % 2 == 0) a[i] /= 2;
			mp[a[i]]++;
		}

		sort(b + 1, b + n + 1, greater<int>());
		int f = 1;
		for (int i = 1; i <= n; i++)
		{
			while (b[i] && mp[b[i]] == 0)
				b[i] /= 2;
			if (b[i] == 0) f = 0;
			else mp[b[i]]--;
		}

		if (f) cout << "YES\n";
		else cout << "NO\n";
	}


	return 0;
}