一、题目
You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.
Example 1:
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
Example 2:
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
Example 3:
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
Constraints:文章来源:https://www.toymoban.com/news/detail-805614.html
1 <= people.length <= 5 * 104
1 <= people[i] <= limit <= 3 * 104文章来源地址https://www.toymoban.com/news/detail-805614.html
二、题解
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
int res = 0;
sort(people.begin(),people.end());
int l = 0,r = people.size() - 1;
while(l <= r){
int sum = l == r ? people[l] : people[l] + people[r];
if(sum > limit) r--;
else if(sum <= limit) l++,r--;
res++;
}
return res;
}
};
到了这里,关于LeetCode881. Boats to Save People的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!