[数据结构与算法]codeforces 1512 B. Box Fitting（1300，贪心）

链接：https://codeforces.com/problemset/problem/1498/B

题意：

给你n个高度为1，长度不定（最大值不会超过盒宽）的方块，放在宽度为W的盒子中，问你最少放几层。

题解：

贪心；从大到小排列，每次放在最空的地方，如果放不下就加一层；我是用数组存方块宽度，用优先队列的值来表示每层剩余空间，最后输出队列的大小就是答案；

PS：暴力会超时。。。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int cnt[100005] = { 0 };
bool cmp(int a, int b)
{
	return a > b;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		priority_queue<int, vector<int>, less<int>>s;
		memset(cnt, 0, sizeof(cnt));
		int n, wid;
		cin >> n >> wid;
		for (int i = 0; i < n; i++)
		{
			cin >> cnt[i];
		}
		sort(cnt, cnt + n, cmp);
		int ans = 1;
		int num = wid;
		for (int i = 0; i < n; i++)
		{
			if (!s.size())
			{
				s.push(wid - cnt[i]);
			}
			else
			{
				if (s.top() - cnt[i] >= 0)
				{
					int temp = s.top() - cnt[i];
					s.pop();
					s.push(temp);
				}
				else
				{
					s.push(wid - cnt[i]);
				}
			}
		}
		cout << s.size() << endl;
	}
}