难度：★★★★☆
类型：数组
方法：数学

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)
提示：

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000

解答

我们先把所有人的体重从小到大做排序，用一个计数器boat记录当前所需要的船的数量。题目中有个暗含的前提，就是每个人都可以上船，而且每艘船要么载一个人，要么载两个人，对于排好顺序后的人，每来一艘船，我们先让最重的上去，然后看看能不能塞下最轻的，如果能，则这搜船坐两个人，否则这搜船只载那个最重的。

class Solution:
    def numRescueBoats(self, people, limit):

        people = sorted(people)
        thin, heavy = 0, len(people) - 1
        boat = 0

        while thin <= heavy:
            if people[heavy] + people[thin] <= limit:
                heavy -= 1
                thin += 1
                boat += 1
            else:
                assert people[heavy] <= limit, "这个人没救了{}".format(people[heavy])
                heavy -= 1
                boat += 1

        return boat

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析