P3122. 快递货车

解题思路

核心思想

为了能够尽可能地装下更多数量的快递，同时不能让货车超载，我们贪心地从小重量的快递开始装载。

具体步骤

1. 将快递按重量从小到大排序。 2. 依次装载快递，并累积当前快递的重量和 cur_weight。 3. 直到 cur_weight 大于货车的最大运载量 max_weight 时，当前所运载的快递数目即为答案。

关键术语

• 贪心策略：优先装载小重量快递，以最大化装载数量。
• cur_weight：当前已装载快递的总重量。
• max_weight：货车允许的最大运载量。

关键结论

当 cur_weight 首次超过 max_weight 时，已装载的快递数量即为最终答案。

思路展开 代码的实现只有三步。第一步，把所有快递的重量读入数组 lst 并从小到大排序，让重量小的快递排在前面。第二步，用 cur_weight 记录当前已装上车的总重量、ans 记录已装载的快递个数，从最轻的快递开始依次尝试装车：每次先把当前快递重量 w 累加进 cur_weight，若累加后严格超过了最大载重量 max_weight，说明这件快递装不下，立刻 break 退出循环，此时 ans 不再增加；若没有超过，则 ans 加 1，继续看下一件。第三步，输出 ans。 这个贪心为什么正确：要装下尽可能多的快递，任何一个装 k 件的方案，都可以换成装最轻的那 k 件，总重量只会更小或不变，所以从最轻的开始装、直到装不下为止，得到的件数一定是最多的。另外注意代码里是先累加再判断、判断超载在先、计数在后，这保证了总重恰好等于载重上限时快递仍能正常装入（只有严格超过 max_weight 才停止）。

复杂度分析 设 n 为快递数量（题面约定最多 1000 个）。

• 时间复杂度：O(n log n)，瓶颈在对重量数组的排序；之后的装车过程只是一次最多 n 步的线性扫描。
• 空间复杂度：O(1)，除输入数组外只用了 cur_weight、ans 两个额外变量。