建设部网站如何下载国标规范,电商网站如何做seo,模板网站开发定制,学了3个月ui好找工作吗给定数组 people 。people[i]表示第 i 个人的体重 #xff0c;船的数量不限#xff0c;每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人#xff0c;但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。 示例 1#xff1a;
输入#…给定数组 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 * 1041 people[i] limit 3 * 104
思路
贪心算法对给定数组进行排序后从左边第一个开始跟右边最后一个进行配对由于每艘船最多载两人如果当前最轻的人和最重的人加起来超过了limit说明重的人可以自己做一辆船轻的人再和下一个人进行配对这样可以保证尽可能地让船载两个人
代码
class Solution {public int numRescueBoats(int[] people, int limit) {int sum0;Arrays.sort(people);int l 0;int r people.length - 1;while (r l) {if (people[l] people[r] limit) {l;}r--;sum;}return sum;}
}
