[数据结构与算法]C. Alice and the Cake

题目链接：C. Alice and the Cake

题意: 爱丽丝有一块蛋糕，她要把蛋糕切成n份，每一次操作，她会选择一块蛋糕(另大小为A)，将其切成两半，两块大小分别为A / 2, (A + 1) / 2,及分成整数的两半，如果原大小为奇数，则一块会大1，现在给出一个序列，问有没有可能为一块蛋糕经过n - 1次操作后得到的

方法一.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		//优先队列,从大到小进行排列 
		priority_queue <ll,vector<ll>,less<ll> >q1;
		//q1队列存的为初始值 
		priority_queue <ll,vector<ll>,less<ll> >q2;
		//q2队列存的是转换后的值 
		ll sum=0;
		for(int i=0;i<n;i++)
		{
			int x;
			cin>>x;
			sum+=x;
			q1.push(x);
		}
		q2.push(sum);//将和推入队列q2中 
		int s=0,f=0;
		while(q1.size()>0)//当q1队列为空时，跳出循环, 
		{
			ll h=q2.top();
			q2.pop();
			if(h==q1.top())//如果h为q1队列的最大的数,将h从q1中删去 
			q1.pop();
			else//如果h不为q1队列的最大值，则将其进行转换 
			{
				s++;
				q2.push(h/2);
				q2.push((h+1)/2);
			}
			if(s>n-1)//满足q1队列不为空且转换次数用完,则输出NO 
			{
				cout<<"NO"<<endl;
				f=1;
				break;
			}
		}
		if(!f)
		cout<<"YES"<<endl;
	}
}

方法二

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll t,a[N],m,n,sum;
map<ll,int>mp;
void dfs(ll x)
{
    if(n==0||m)
    return;
    if(mp[x])
	{
       n--;
       mp[x]--;
       return;
    }
    if(x==1){
        m=1;
        return;
    }
    dfs(x/2);
    dfs(x-x/2);
}
int main()
{ 
      cin>>t; 
      while (t--)
      {
            cin>>n;
            sum=0;
            m=0;
            mp.clear();
            for(int i=1;i<=n;i++)
            {
                cin>>a[i];
                sum+=a[i];
                mp[a[i]]++;
            }
            dfs(sum);
            if(n)
            puts("NO");
            else
            puts("YES"); 

      }
      
    
}