1. 題目

第 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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/boats-to-save-people
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 將重量排序，設置雙指針在首尾
• 優先裝兩個重量大的，裝不下就嘗試一個最大的和一個最小的

class Solution { public:int numRescueBoats(vector<int>& people, int limit) {sort(people.begin(), people.end());int i = 0, j = people.size()-1, count = 0, w = 0, p = 0;while(i <= j){while(j >= 0 && p < 2 && w+people[j] <= limit){w += people[j];++p;//一條船最多兩人--j;}while(i <= j && p < 2 && w+people[i] <= limit){w += people[i];++p;++i;}count++;p = 0;w = 0;}return count;} };

總結

以上是生活随笔為你收集整理的LeetCode 881. 救生艇（贪心，双指针）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。