0881. Boats to Save People¶
题目信息¶
- 题号:
0881
- 难度:
Medium
- 主题:
人员分组、载重限制、最少船数
- 原题:
- 重点:
每艘船最多载两个人且总重量不能超过 limit;每个人必须恰好登上一艘船,返回最少船数
题目重述¶
给定数组 people,其中每个元素表示一个人的体重,以及每艘救生艇的载重上限 limit。每艘船最多乘坐两个人,并且船上人员总重量不能超过 limit。
需要让所有人都登船,每个人恰好乘坐一艘船,船的数量不限。请返回完成救援所需的最少救生艇数量。题目保证每个人的体重都不超过载重上限,因此单独乘船总是可行。
1 <= people.length <= 5 * 10^4,1 <= people[i] <= limit <= 3 * 10^4。
自建示例¶
只能有一对能够同船:
输入:people = [1,2,2,3], limit = 3
输出:3
解释:可以让体重 1 和其中一名体重 2 的人同船,另一名体重 2 的人和体重 3 的人分别单独乘船,共三艘;任何船都不能载三人。
只有一名人员且体重达到上限:
输入:people = [4], limit = 4
输出:1
解释:人员数量达到允许的最小值,且唯一人员可以单独乘船。至少需要一艘船,因此答案为 1。