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;
	}
}

全部评论

相关推荐

完美的潜伏者许愿简历...:隐藏信息被你提取出来了,暗示,这就是暗示
点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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