题目
给定数组 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
二分查找
分析法
最少船数=人数-最多搭伙坐船数。如果能搭伙m组人，则还需要计算能否搭伙更多的船，左闭右开空间。
代码
class Solution { public: int numRescueBoats(vector& people, int limit) { sort(people.begin(), people.end()); int left = 0, right = people.size() / 2 + 1;//左闭右开空间 while (right - left > 1) { const int mid = left + (right - left) / 2; if (Is(people, mid, limit)) { left = mid; } else { right = mid; } } return people.size() - left; } bool Is(const vector& people, int num, int limit) { for (int i = 0; i < num; i++) { if (people[i] + people[num * 2 - 1 - i] > limit) { return false; } } return true; } };
测试用例
void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector people; int limit, res; { people = { 3,2,3,2,2 }; limit = 6; Solution slu; auto res = slu.numRescueBoats(people, limit); Assert(3, res); } { people = { 1, 2 }; limit = 3; Solution slu; auto res = slu.numRescueBoats(people, limit); Assert(1, res); } { people = { 3,2,2,1 }; limit = 3; Solution slu; auto res = slu.numRescueBoats(people, limit); Assert(3, res); } { people = { 3,5,3,4 }; limit = 5; Solution slu; auto res = slu.numRescueBoats(people, limit); Assert(4, res); }
//CConsole::Out(res);
}
双指针
分析
排序后，left和right合伙坐船，left <= right时结束。如果有多人能和left合伙，取体重最重的。随着left增加，right减少。
代码
class Solution { public: int numRescueBoats(vector& people, int limit) { sort(people.begin(), people.end()); int left = 0,right = people.size()-1; while (left < right ) { while ((right > left) && (people[left] + people[right] > limit)) { right–; } if (right > left) { left++; right–; } } return people.size() - left; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
