定制架子问题（简单）

定制架子问题
【题目描述】
李莳花要做一个架子，把她喜欢的摆件叠放起来，她的每个摆件的位置顺序是固定的。这个架子的宽度是 W，每层排放的摆件不能超过这个宽度，每层架子的高度不能低于最高的摆件的高度。假设，给出排列好的每个摆件的宽度Wi，和高度Hi，请计算需要最少多高的架子。
【输入格式】
输入的第一行有 2 个数字，一个是摆件的个数 n，和架子的宽度W。以下摆件个数 n 行，每行的第一个数是摆件的宽度 Wi和高度Hi。【输出格式】
输出放置摆件架子的最低高度。
【样例输入】（测试数据不包含本样例）
5 5
2 1
1 2
1 3
2 3
2 2
【样例输出】
5
请教高人思路，歇半天没写对

这个问题你没有给出题目的数据量级，那我就默认使用贪心算法来解决。贪心算法在这个问题中的时间复杂度为O(nlogn)，其中n是摆件的数量。首先，我们需要按照摆件的高度进行排序。
按照以下步骤进行摆放：

1. 初始化当前架子的高度为0
2. 从最矮的摆件开始，依次遍历每个摆件
3. 如果当前摆件的宽度加上当前架子的宽度小于等于架子的宽度W，那么将当前摆件放在当前架子上，并更新当前架子的宽度为当前摆件的宽度加上当前架子的宽度。
4. 如果当前摆件的宽度加上当前架子的宽度大于架子的宽度W，那么需要另起一层架子。将当前摆件放在新的一层架子上，并更新当前架子的宽度为当前摆件的宽度，并将当前架子的高度加上当前摆件的高度。
5. 重复步骤3和步骤4，直到遍历完所有的摆件。
6. 返回当前架子的高度作为结果。

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7471289
• 除此之外, 这篇博客: 单素数判断（根号n后再优化）和俄罗斯农民乘法(带证明），以及埃筛的证明中的 简单解释下普遍大家都知道的（给新手），就是为啥只到根号n。最开始其实终止条件是到n/2的，很简单嘛，因为n/2之后不可能存在n的因子，因为最小的因子2乘上一个任何一个大于n/2的数肯定比n大，所以之后不存在因子。那为啥能筛到根号n呢，是因为根号n的平方是n本身，根号n后面如果存在n的因子a，那么一定能在n之前找到n/a这个因子，只要有因子就不是素数了，所以没必要反复筛，前面筛完就已经知道不是素数了 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• #include<bits/stdc++.h>
  using namespace std;
  int main() 
  {
  	int n;
  	cin>>n;
  	if(n==2||n==3)
  	{
  		cout<<"是素数";
  	}
  	else if(n%6!=1&&n%6!=5)
  	{
  		cout<<"不是素数";
  	}
  	else
  	{
  		for(int i=2;i*i<=n;i++)
  		{
  			if(!(n%i))
  			{
  				cout<<"不是素数" ;
  				return 0;
  			}
  		}
  		cout<<"是素数";
  	}
  }