P3118. 租车骑绿岛

解题思路

注意，本题和 救生艇 完全一致，甚至连示例都和原题里的示例二一致。

核心思想

整个题目的贪心思想，其实可以用一句话解释清楚： 当我们考虑一个较轻的人时，我们总是贪心地想让它和一个较重的人进行配对。

因为如果是两个较轻的人组队，那么可能会出现重的人无法配对的情况，从而减少了分组数。 因此我们希望尽量使用 一轻一重 这样的搭配，来使得每一组的剩余空间尽可能少，从而使得分组数尽可能地多。

实现策略

因此 排序 + 贪心 + 双指针 的策略就呼之欲出了。

思路展开 先把所有人的体重从小到大排序，再设置一对相向而行的双指针：left 指向当前最轻的人，right 指向当前最重的人，ans 记录已经派出的船数。每一轮循环只做一个判断：

• 若 nums[left] + nums[right] <= m，说明当前最轻和最重的两个人可以同坐一条船，两人一起上船，left 加 1、right 减 1，ans 加 1。
• 否则说明连最轻的人都陪不了这个最重的人，那么最重的人只能单独占一条船，right 减 1，ans 加 1。

之所以总让最重的人优先尝试带上最轻的人，是因为如果连最轻的人都带不动，那换任何人都带不动，最重的人必然单独坐船；而如果带得动，让他带走最轻的人，剩下的人两两配对的余地只会更大、不会更差。循环条件是 left <= right，取等号保证中间剩下最后一个人时，他也会单独占一条船。循环结束时每个人都恰好被安排过一次，ans 即最少船数。

复杂度分析 设 n 为人数。

• 时间复杂度：O(n log n)，瓶颈在排序；排序后的双指针循环中，left 与 right 每轮至少有一个移动，最多执行 n 轮，只需 O(n)。
• 空间复杂度：O(1)，只用了 left、right、ans 等常数个额外变量（不计输入数组与排序内部开销）。