Leetcode(885)- 救生艇
2024-08-24 15:59:00
第 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
思路:利用贪心算法,尽量先载比较重的,然后尽量看能不能将小的和重的拼成一个。这样会用到最少的船数。所以应该先对人按重量大小排个序,然后从大的开始,另外一头从小的开始,尽量和大的能拼成一个。
int numRescueBoats(vector<int>& people, int limit)
{
sort(people.begin(),people.end());//排序,这样是从小到大排好序
int left = 0,right = people.size() - 1,result = 0;
while(left < right)
{
if(people[left] + people[right] <= limit)//如果能拼,就用一条船
{
result++;
left++;
right--;
}
else //如果不行,就让重的单独用一条船
{
result++;
right--;
}
}
if(left == right) {//只剩下一个人的时候,肯定还是要单独用一条
result++;
}
return result;
}
最新文章
- <;三>;JDBC_面向对象思想的体现
- 使用SQL Server维护计划实现数据库定时自动备份
- Android控件系列之CheckBox
- NodeJs多进程和socket.io通讯-DEMO
- JavaBean与EJB的区别与应用
- enode框架step by step之Staged event-driven architecture思想的运用
- 如何将angular-ui的图片轮播组件封装成一个指令
- Swift2
- crontab定时任务(centos)
- Java中判断是否为空的方法
- Jar 初步
- 写入一个html文件时的编码要求
- js 操作对象 记录
- 22.doublewrite/ChangeBuffer/AHI/FNP
- MVC登录前准备写好cookie
- Node复制文件
- html 更新
- Centos 6.5 Install Mysql 8.0.0
- CentOS7下安装VLC
- ubuntu下使用sdk manager 安装sdk 其他版本
热门文章
- python3.8.1安装cx_Freeze
- 03. struts2中Action配置的各项默认值
- 夯实基础系列一:Java 基础总结
- 小白都看得懂的Javadoc使用教程
- What is :: (double colon) in Python when subscripting sequences?
- Linux的.a、.so和.o文件 windows下obj,lib,dll,exe的关系 动态库内存管理 动态链接库搜索顺序 符号解析和绑定 strlen函数的汇编实现分析
- 安装、登入centos7
- 一个实体对象不能由多个 IEntityChangeTracker 实例引用
- SpringCloud配置刷新机制的简单分析[nacos为例子]
- noip 注意事项 (个人向)