CF Round#778 C - Alice and the Cake

C - Alice and the Cake

队列/优先队列

  1. 记录每个重量的蛋糕个数

  2. 求出蛋糕的重量之和，看这个重量能否切出这些蛋糕

  3. 把总和放入队列，如果当前这个重量还有蛋糕，那就不切这个，如果没有就继续切

但是这样广搜，很多重量其实是切不出来的，但要一直切到 1 才能判断出来，所以效率很低

因为最多切 \(n-1\) 次，所以每切一次就记录下来，切够 \(n - 1\) 次就不切了

如果用优先队列，维护一个小根堆，小重量很快就可以判断出能不能切出，这样效率也很高

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n;
ll a[N];

int h;
bool flag;
map cnt;


int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		flag = false;
		cnt.clear();
		cin >> n;
		ll sum = 0;
		h = 0;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			cnt[a[i]]++;
			sum += a[i];
		}
		queue q;
		q.push(sum);
		int t = 0;
		flag = true;
		while(!q.empty())
		{
			ll c = q.front();
			q.pop();
			if (cnt[c] > 0)
				cnt[c]--;
			else
			{
				t++;
				ll a = c / 2, b = c - a;
				//cout << t << " " << a S<< " " << b << " " << cnt[a] << " " << cnt[b] << endl;
				if (a >= 2)
					q.push(a);
				else
					cnt[a]--;
				if (b >= 2)
					q.push(b);
				else
					cnt[b]--;
				if (t == n)
					break;
			}
		}
		for (auto i : cnt)
		{
			if (i.second != 0)
			{
				flag = false;
				//cout << i.first << " " << i.second << endl;
			}
		}
		cout << (flag ? "YES" : "NO") << endl;
	}
	return 0;
}
优先队列1400队列数据结构

相关

数据结构--栈（C语言实现）

队列的顺序/链式存储实现

实现延迟消息队列

顺序存储的循环队列（c++实现）

数据结构----单链表升级版

数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

数据结构+java中常用的集合类

数据结构 之二叉树

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

数据结构与算法之PHP排序算法（冒泡排序）

03java算法与数据结构------环形队列代码实现

标签