881. 救生艇 (Medium)
2024-09-08 19:34:20
问题描述
给定数组 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 * 10⁴
1 <= people[i] <= limit <= 3 * 10⁴
解题思路
每次必定选择最轻的的和二者重量和不超过limit
的最重的人上船,因此可以将数组排序,然后一左一右双指针向中间遍历。
代码
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
std::sort(people.begin(), people.end());
int left = 0, right = people.size() - 1;
int cnt = 0;
while (left <= right) {
if (people[right] + people[left] <= limit) {
cnt++;
right--;
left++;
} else {
cnt++;
right--;
}
}
return cnt;
}
};
最新文章
- MMORPG大型游戏设计与开发(客户端架构 part9 of vegine)
- 记一个PowerShell的方法调用 --ResolveWindowsPrincipal
- 带你看懂Dictionary的内部实现
- 设置sudo不输入密码 sudoers 编辑出错后的补救方法
- DELPHI中IDE宏录制小用
- hadoop2.2编程:用ruby跑hadoop的完整实例
- 第2章 开始入手 —— 01 创建第一个 Android 应用程序
- HDU 5611 Baby Ming and phone number
- CMFCShellList和自定义ShellList结合使用,达到“直接浏览缩略图,双击打开图片”
- Oracle:WITH AS () Merge ?
- springmvc 项目完整示例08 前台页面以及知识点总结
- linux安装kibana
- DNS域名解析之搭建公司内部域--技术流ken
- 2018年最值得关注的30个Vue开源项目
- wap2app(八)-- iphoneX 底部导航的兼容问题
- hadoop安装要领
- BBC记录片之非洲4
- BZOJ.3546.[ONTAK2010]Life of the Party(二分图匹配 ISAP)
- Rpgmakermv(14)Archeia_Steamworks
- python3与python2的区别(目前遇到的)