1498B - Box Fitting (优先队列)

题目

思路:开一个优先队列存放每一行(高度1)还剩余的长度,将所有的木块从大到小排序,1开始遍历,如果优先队列中还能容纳最大的长度比当前木块大则加入到当前高度所在行,否则另开一行存放。

Code:

#include<iostream>
#include<algorithm>
#include<set>
#define ll long long
using namespace std;
const int Max = 1e6 + 5;
int lst[Max];

int main()
{
   
	int t;cin >> t;
	while (t--)
	{
   
		int n, w;cin >> n >> w;
		for (int i = 1;i <= n;i++)cin >> lst[i];
		sort(lst + 1, lst + 1 + n, greater<int>());
		multiset<int,greater<int>> set;
		set.insert(w);
		for (int i = 1;i <= n;i++)
		{
   
			int a = *set.begin();
			if (a >= lst[i])
			{
   
				set.insert(a - lst[i]);
				set.erase(set.find(a));
			}
			else set.insert(w - lst[i]);
		}
		cout << set.size() << endl;
	}
}

全部评论

相关推荐

07-07 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 13:54
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务