[C++知识库]C. Alice and the Cake 日常水题

先码上自己的正确代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
priority_queue<ll>q1;//q1放未配对的元素，就是待分割匹配的元素，初始放个所有数的合数
priority_queue<ll>q2;//q2放未配对的元素，即初始数组的元素，一个个对照q1消去
int main()
{
	int N;
	cin >> N;
	while (N--)
	{
		while (!q1.empty())
			q1.pop();
		while (!q2.empty())
			q2.pop();
		int n;
		cin >> n;
		ll temps = 0;
		for (int i = 0; i < n; i++)
		{
			ll a;
			cin >> a;
			q2.push(a);
			temps += a;
		}
		int flag = 0;
		q1.push(temps);
		while (!q2.empty())
		{
			ll temp = q1.top();
			q1.pop();
			if (temp==q2.top())
				q2.pop();

			else if (temp < q2.top())
				break;

			else if (q1.size() > q2.size())
				break;

			else
			{
				ll a1 = (temp + 1) / 2;
				ll a2 = temp / 2;
				q1.push(a1);
				q1.push(a2);
			}
		}
		if (q2.empty())
			cout << "YES\n";
		else
			cout << "NO\n";
	}
}

其实想写的原因是想给大家看看我最开始的，暴力的代码，就是从给定数组试图合出最后一个数字，而不是正确解中从合数分割出目标解
下面是暴力的错误解答

#include<bits/stdc++.h>
using namespace std;
int flag = 0;
map<int, int>m;
priority_queue<int, vector<int>, greater<int> >q;
void dfs()
{
	if (q.size() == 1)
	{
		flag = 1;
		return;
	}
	int a = q.top();
	q.pop();
	m[a]--;
	for (int i = 0; i <= 1; i++)
	{
		if (flag)
			break;
		if (m[a+i] == 0)
			continue;
		else
		{
			vector<int>v;
			while ((q.top() != a + i))
			{
				v.push_back(q.top());
				m[q.top()]--;
				q.pop();
			}
			q.pop();
			q.push(a + a + i);
			m[a + i]--;
			m[a + a + i]++;
			
			for (int j = 0; j < v.size(); j++)
			{
				m[v[j]]++;
				q.push(v[j]);
			}

			dfs();
			//状态回溯
			if (!flag)
			{
				vector<int>v1;
				while ((q.top() != a + a + i))
				{
					v1.push_back(q.top());
					m[q.top()]--;
					q.pop();
				}
				m[a + a + i]--;
				q.pop();
				for (int j = 0; j < v1.size(); j++)
				{
					m[v1[j]]++;
					q.push(v1[j]);
				}
			}
			q.push(a + i);
			m[a + i]++;
		}
	}
	q.push(a);
	m[a]++;
	return;
}
int main()
{
	int N;
	cin >> N;
	while (N--)
	{
		while (!q.empty())
			q.pop();
		m.clear();
		flag = 0;
		int n;
		cin >> n;
		while (n--)
		{
			int i;
			cin >> i;
			q.push(i);
			m[i]++;
		}
		dfs();
		if (flag)
			cout << "YES";
		else
			cout << "NO";
		cout << endl;
	}
}

u1s1，dfs里面的状态回溯我感觉写得还挺不错的，虽说debug花了我好久时间，主要原因是几个重新push进去的步骤顺序错了。导致最后队列总是空了。
比如1+2=3，开始放3进去队列，状态回溯的时候，把3还原成1和2，总是有1个1或者2忘记放回数组中去