题目分析

琪儿需要放 N 本书到一个宽度为 Sw 的书架上，书的宽度和高度已知，且书的顺序不能改变。问题的目标是计算放置这些书所需要的最小高度。

思路

1. ​问题理解​：
   • 给定每本书的宽度 Wi 和高度 Li，书架的最大宽度是 Sw。
   • 书必须按照顺序排放在书架上，不能打乱顺序。
   • 书架上每一层的宽度之和不能超过 Sw，如果某一层的宽度已经满了，剩余的书就放到下一层。
   • 目标是计算最小的书架高度，书架的高度等于放置书的层数的总和。
2. ​解决方案​：
   • ​贪心策略​：我们从左到右依次放书，每次尝试把当前书放到当前层。如果当前层放不下，则开始新的一层。
   • 具体步骤：
     • 维护一个变量 current_width 表示当前层的总宽度。
     • 维护一个变量 total_height 表示当前已经用掉的高度。
     • 遍历每一本书：
       • 如果当前书能够放进当前层（即 current_width + Wi ≤ Sw），则把它放进去。
       • 如果当前书放不下，则开始新的一层，增加总高度。
3. ​边界条件​：
   • 如果书只有一层，那就是一个层的高度。
   • 如果书的宽度可以正好填满每一层的最大宽度，层数可能等于书的数量。

复杂度分析

• ​时间复杂度​：O(N)，遍历每一本书，逐一判断是否能放入当前层。
• ​空间复杂度​：O(1)，只用了常数级别的空间。

示例

​输入​：

5 5
2 1
1 2
1 3
2 3
2 2

​输出​：

5

​解释​：

• 第1层放 2 1 和 1 2，总宽度为 2 + 1 = 3，最大高度为 2。
• 第2层放 1 3，2 3 和 2 2，总宽度为 1 + 3 + 2 = 6，所以第二层开始新的一层，最大高度为 3。

所以总高度是 2 + 3 = 5。