881. 救生艇 Medium

本文主要是介绍881. 救生艇 Medium，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定数组 people 。people[i]表示第 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 <= 5 * 104

 ·1 <= people[i] <= limit <= 3 * 104

题目大意：在每艘船只能乘坐两人且承重为limit的情况下计算承载所有人最少需要的船量。

分析：

（1）对people数组按升序排序，体重最轻的人若能与体重最重的人乘同艘船，则体重最轻的人可以与其他任何人同船，此时考虑两种情况：①体重最轻的人people[0]与体重最重的人people[N-1]同船；②体重最轻的人people[0]与体重较重的人people[k](0<k<N-1)同船；

（2）对于第一种情况的剩余人员是people[1:k-1]、people[k]、people[k+1:N-2]，对于第二种情况的剩余人员是people[1:k-1]、people[k+1:N-2]、people[N-1]，显然两种情况的剩余人员只有1个人不同，第一种情况是people[k]，第二种情况是people[N-1]，由于people[k]<=people[N-1]，因此第一种情况的最少需要的船只<=第二种情况最少需要的船只；

（3）由（2）种结论可得，若最重的人可以与最轻的人同船时，将此二人放在同艘船上是最优解。

class Solution {
public:int numRescueBoats(vector<int>& people, int limit) {int N=people.size(),ans=0;sort(people.begin(),people.end());for(int l=0,r=N-1;l<=r;--r){if(people[l]+people[r]<=limit) ++l;++ans;}return ans;}
};

这篇关于881. 救生艇 Medium的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---