PART_2_力扣图解/sourcefile/14.其他补充题目/06.md
date: 2020-06-16
小浩算法改版了，大家看一下风格怎么样，还喜欢吗？所有的排版，绘图，文案，题解都是由小浩一人完成哦~
今天为大家分享一道关于 “救生艇” 的题目。
话不多说，直接看题吧。
| 第881题：救生艇 |
|---|
| 第 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)
提示：
这不是一道算法题，这是一个脑筋急转弯。
一个船最多可以装两个人，并且不能把船压垮。同时要求把这些人可以统统装下的最小船数。用脚趾头也可以想到，我们需要尽最大努力的去维持一个床上得有两个人。。哦，不，船上。这是什么思想？Bingo，贪心。
思路很简单：
根据分析，得到代码：
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int i = 0, j = people.length - 1;
int ans = 0;
while (i <= j) {
ans++;
if (people[i] + people[j] <= limit)
i++;
j--;
}
return ans;
}
}
GO代码其实也一样：
func numRescueBoats(people []int, limit int) int {
sort.Ints(people)
ans ：=0
i, j :=0, 0, len(people) - 1
for i <= j {
if people[i] + people[j] <= limit {
i++
} else{
j--
}
ans++
}
return ans
}
这里肯定马上就有细心的读者会问！为什么你每次是让最瘦的和最胖的来凑一对。而不是放弃掉这个最瘦的，去找一个逼近limit体重的人来乘船呢？这里要注意题目，因为题中已经告诉了， 一艘船仅能坐两人。所以去找一个逼近limit体重的人是没有意义的。
但是，这里并不妨碍我们将此题扩展进行思考。这里留下疑问，如果我们不对船上的人数进行限制，那么应该如何来完成本题呢？大家可以尝试代码练习一下。