莱芜建设银行网站,网页工具栏,做爰网站名称,wordpress首页幻灯片插件1. 题目
第 i 个人的体重为 people[i]#xff0c;每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人#xff0c;但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
示例 1#xff1a;
输入#xff1a;peopl…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(vectorint 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 wpeople[j] limit){w people[j];p;//一条船最多两人--j;}while(i j p 2 wpeople[i] limit){w people[i];p;i;}count;p 0;w 0;}return count;}
};
