贪心算法

买苹果

方法思路

问题分析：题目要求从一堆苹果中选出尽可能多的苹果，使得它们的总重量不超过给定的限制。贪心算法适用于此类问题，因为选择重量小的苹果可以最大化数量。

算法选择：将苹果按重量升序排序后，依次选择重量最小的苹果，直到无法再添加更多苹果而不超过重量限制。

复杂度分析：排序的时间复杂度为O(n log n)，遍历数组的时间复杂度为O(n)，总体复杂度为O(n log n)，适用于给定的约束条件。

---

津津铺草坪

方法思路

问题分析：道路长度为40米，宽度为2米，与草坪的宽度相同，因此只需考虑草坪的长度。目标是选择尽可能少的草坪块，使它们的总长度至少为40米。

算法选择：采用贪心算法，优先选择长度最长的草坪块，这样可以尽快达到40米的要求，从而最小化草坪块的数量。

复杂度分析：排序草坪块的时间复杂度为O(n log n)，遍历草坪块的时间复杂度为O(n)，总体复杂度为O(n log n)，适用于给定的约束条件（n < 100）。

---

李老师的书架

方法思路

问题分析：书架的高度为B，我们需要从N个学生中选择尽可能少的学生，使得他们的总高度至少为B。每个学生的高度不同，选择高个子的学生可以更快达到目标。

算法选择：将学生按身高降序排序，然后从高到低依次累加身高，直到总高度达到或超过B。此时累加的学生数量即为所求。

复杂度分析：排序学生身高的时间复杂度为O(N log N)，遍历学生的时间复杂度为O(N)，总体复杂度为O(N log N)，适用于给定的约束条件（N ≤ 20,000）。

---

希蒙的宝藏

方法思路

问题分析：毛驴的承重上限为w，有s种宝物，每种宝物有总重量和总价值。宝物可以分割，因此我们需要优先选择单位价值最高的宝物来最大化总价值。

算法选择：计算每种宝物的单位价值（价值/重量），并按单位价值降序排序。然后依次选择宝物，尽可能多地取单位价值高的宝物，直到达到承重上限。

复杂度分析：排序宝物的时间复杂度为O(s log s)，其中s是宝物种类数。处理每种宝物的时间复杂度为O(s)，总体复杂度为O(s log s)，适用于给定的约束条件（s ≤ 100）。

---

津津的宝石矿场

---

希蒙的教室用电