B. Box Fitting

B. Box Fitting

题意：

现在有n个长方形，宽均为1，现在有一个底为m的容器，问将长方形放入其中，所用容器的最小宽度是多少
（长方形必须长朝下放置详细如图）

题解：

比赛时脑子抽了。。。
我想的是，先排序，对于第一层依次放长的，如果长的放不下就依次放短的，我想的是让短的取填空隙，但是wa了我也不知道为啥
今天补题，感觉每次只需要找仅小于当前长度的长方形即可
这样放就是尽可能放大的，实在放不了大的再开新一层

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=1e5+9;
int a[maxn];
vector<int>vec;
int main()
{
	int t;
	cin>>t;
	while(t--){
		ll n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			vec.push_back(x);
		}
		sort(vec.begin(),vec.end());
		ll num=m;
		int tot=0;
		while(vec.size())
		{
			int pos=upper_bound(vec.begin(),vec.end(),num)-vec.begin();
			pos--;
			if(pos==-1)
			{
				num=m;
				tot++;
				continue;
			}
			else 
			{
				num-=vec[pos];
				vec.erase(vec.begin()+pos);
				 
				continue;
			}
			
		}
		cout<<tot+1<<endl; 
	}
	return 0;
}