[C++知识库]C. Alice and the Cake（思维/模拟）

Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)

题目

输入

14
1
327
2
869 541
2
985214736 985214737
3
2 3 1
3
2 3 3
6
1 1 1 1 1 1
6
100 100 100 100 100 100
8
100 100 100 100 100 100 100 100
8
2 16 1 8 64 1 4 32
10
1 2 4 7 1 1 1 1 7 2
10
7 1 1 1 3 1 3 3 2 3
10
1 4 4 1 1 1 3 3 3 1
10
2 3 2 2 1 2 2 2 2 2
4
999999999 999999999 999999999 999999999

输出

YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES

思路

模拟完整的蛋糕切割过程。
开两个优先队列a，b（大根堆）。a队列存当前已经分割好的蛋糕（输入的数据），b队列每次枚举体积最大的蛋糕，将其切成两块存入b队列。注意对b数组进行操作前需要先将a，b队列中队头相同的部分pop掉。最终如果两个队列均为emoty，则表明有解，否则表面无解。

CODE

priority_queue<ll>a, b;
int main()
{
	IOS;
	int T; cin >> T;
	while (T--)
	{
		while (!a.empty()) a.pop();
		while (!b.empty()) b.pop();

		int n; cin >> n;
		ll sum = 0;
		for (int i = 1, x; i <= n; i++)
			cin >> x, a.push(x), sum += x;

		b.push(sum);
		int cnt = n;
		while (cnt--)
		{
			if (a.empty() || b.empty())
				break;
			while (!a.empty() && !b.empty() && a.top() == b.top())
				a.pop(), b.pop();
			
			ll x = 0, y = 0;
			if (!b.empty())
				x = b.top() / 2, 
				y = (b.top() + 1) / 2,
				b.pop();
			

			if (x && y)
				b.push(x), b.push(y);
		}

		if (a.empty() && b.empty()) cout << "YES\n";
		else cout << "NO\n";
	}


	return 0;
}