【3.6】贪心算法-解救生艇问题

一、题目

        第 i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit。 每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit 返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

二、解题思路

        题目要求每艘船最多能载两人,为了使船的使用数量最少,我们应尽可能地让每艘船载两人。解决这个问题的策略是首先对数组进行排序,然后优先考虑体重最重的个体。

具体步骤如下:
1. **排序**:将数组中的体重按从小到大的顺序排列。
2. **配对**:从体重最重的个体开始,检查其是否能与体重最轻的个体同乘一船。如果能,则让他们同乘;如果不能,则体重最重的个体只能单独乘船。
3. **迭代**:继续上述过程,依次考虑体重次重的个体,直到所有人都被分配到船上。

通过这种策略,我们可以最大限度地利用每艘船的载人能力,从而减少船的总使用数量。

三、代码实现

#include <iostream>
#include <vector>
#include <algorithm>int numRescueBoats(std::vector<int>& people, int limit) {// 先对数组进行排序(人发重量按照从小到大的顺序排序)std::sort(people.begin(), people.end());// 统计船的个数int count = 0;// 从小到大排序,左边的是最小的,右边的是最大的int left = 0;int right = people.size() - 1;while (left <= right) {// 如果体重最大的和体重最小的可以单独乘坐// 一条船,就让他们同乘一条船if (people[right] + people[left] <= limit)left++;// 体重最大的每次都要减1right--;// 使用船的数量count++;}return count;
}int main() {std::vector<int> people = {3, 2, 2, 1};int limit = 3;int result = numRescueBoats(people, limit);std::cout << "Number of boats needed: " << result << std::endl;return 0;
}

时间复杂度

  1. 排序:使用std::sort函数对数组进行排序。在C++中,std::sort通常使用的是快速排序(QuickSort)、堆排序(HeapSort)或插入排序(InsertionSort)的混合算法,其平均时间复杂度为 O(nlog⁡n),其中 n 是数组的长度。

  2. 双指针遍历:使用双指针从两端向中间遍历数组。这个过程的时间复杂度是 O(n),因为每个元素最多被访问一次。

综合起来,整个算法的时间复杂度是 O(nlog⁡n),主要由排序部分决定。

空间复杂度

  1. 排序std::sort的空间复杂度取决于其实现方式。通常情况下,快速排序的空间复杂度是 O(log⁡n),而堆排序的空间复杂度是 O(1)。C++标准库中的std::sort通常会使用一些额外的空间,但不会超过 O(log⁡n)。

  2. 双指针遍历:双指针遍历本身不需要额外的空间,空间复杂度是 O(1)。

综合起来,整个算法的空间复杂度是 O(log⁡n),主要由排序部分决定。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/412281.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【58同城-注册安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞 …

【零知识证明】MiMC哈希函数电路

1 哈希电路 哈希函数电路实现&#xff1a; pragma circom 2.0.0;// y (x k c) ^ 5 // 输入信号x, k &#xff0c;常量c // base x k c // base2 base * base // base4 base2 * base2 // base5 base *base4 // 输出 ytemplate MIMC5(){signal input x;signal input k…

【SpringCloud Alibaba】(九)学习 Gateway 服务网关

目录 1、网关概述1.1、没有网关的弊端1.2、引入 API 网关 2、主流的 API 网关2.1、NginxLua2.2、Kong 网关2.3、Zuul 网关2.4、Apache Shenyu 网关2.5、SpringCloud Gateway 网关 3、SpringCloud Gateway 网关3.1、Gateway 概述3.2、Gateway 核心架构 4、项目整合 SpringCloud …

信息安全--网络安全体系与安全模型(二)

其他安全模型 ■纵深防御模型&#xff1a;①安全保护②安全监测③实时响应④恢复 ■分层防护模型&#xff1a;参考OSI模型&#xff0c;对保护对象进行层次化保护。 ■等级保护模型&#xff1a;将信息系统划分成不同安全保护等级&#xff0c;采取相 应的保护措施。 ■网络生…

UE开发中的设计模式(四) —— 组合模式

面试中被面试官问到组合模式和继承有什么区别&#xff0c;给我问懵了&#xff0c;今天又仔细看了下&#xff0c;这不就是UE里的组件吗 >_< 文章目录 问题提出概述问题解决总结组合模式的优缺点继承的优缺点 问题提出 考虑这样一个场景&#xff0c;我们有一个敌人的基类&…

武器弹药制造5G智能工厂物联数字孪生平台,推进制造业数字化转型

武器弹药制造领域作为国防工业的重要组成部分&#xff0c;其数字化转型更是关乎国家安全与军事实力提升的关键。随着5G、物联网、大数据、云计算及人工智能等先进技术的融合应用&#xff0c;武器弹药制造5G智能工厂物联数字孪生平台应运而生&#xff0c;正逐步成为推进制造业数…

程序设计—智慧城市应急物资配送系统开发—大数据模块 项目源码36262

摘 要 智慧城市应急物资配送系统开发中的大数据模块&#xff0c;作为核心的数据处理与分析组件&#xff0c;实现了数据可视化、用户行为分析、精准广告推送、数据报表生成以及商品与需求信息的全面管理。 该模块通过数据地图展示大屏&#xff0c;实时呈现应急物资配送的层级联…

【STM32】电容触摸按键

电容按键就是酷&#xff0c;但据我使用过电容按键版的洗澡计费机子后&#xff0c;一生黑&#xff08;湿手优化没做好的电容按键简直稀碎&#xff09;。 大部分图片来源&#xff1a;正点原子HAL库课程 专栏目录&#xff1a;记录自己的嵌入式学习之路-CSDN博客 目录 1 触摸按…

Python 如何操作 Excel 文件(openpyxl, xlrd)

Python是处理Excel文件的一种非常强大且灵活的工具&#xff0c;尤其是通过使用openpyxl和xlrd等库。openpyxl专注于Excel 2007及更高版本的.xlsx文件的创建、读取、修改和写入&#xff0c;而xlrd则主要用于读取早期版本的Excel文件&#xff08;.xls&#xff09;&#xff0c;但自…

【教你一键解决】draw.io中输入英文显示成中文且输入位置移到首位

问题描述&#xff1a;当英文输入一个“a”时&#xff0c;会自动出现中文“一个”&#xff0c;再输入“a”才会出现“a”&#xff0c;删除时无法把中文删除&#xff0c;如下图所示。 解决方法&#xff1a;关闭浏览器的自动翻译功能即可&#xff0c;如下图所示。

HTTPS协议中的加密机制分析、证书认证

目录 一、为什么要对数据进行加密&#xff1f; 二、什么是加密和解密&#xff1f; 三、加密方式 对称加密 非对称加密 四、数据摘要(数据指纹) 五、数字签名 六、探究保证双方通信安全的的加密方案 1、只使用对称加密 2、只使用非对称加密 3、双方都是用非对称加密 …

怎么理解数据资源、数据资产和数据要素?

身处信息化时代&#xff0c;我们每时每刻都在产生和接触各类数据&#xff0c;如网购记录、短视频等。在我国数据安全法中将数据定义为任何以电子或其他方式对信息的记录。即数据不仅指数字表格等结构化内容&#xff0c;也可以是文字、图形、图像等半结构化、非结构化信息。 1、…

航空制造领域中三维工艺技术的应用

飞机制造企业可以通过三维数字化技术的应用有效提升了工艺设计水平&#xff0c;解决了在航空产品数字化工艺设计、制造方面的标准统一和系统整合等问题&#xff0c;保证了业务应用系统基础数据的一致性和规范性。本文是对航空制造领域中三维工艺技术的应用的介绍。 随着信息化技…

安装JKS格式证书

--千金易得 知己难求 本文介绍如何在Tomcat服务器配置JKS格式的SSL证书&#xff0c;具体包括下载和上传证书文件&#xff0c;在Tomcat上配置证书文件和证书密码等参数&#xff0c;以及安装证书后结果的验证。成功配置SSL证书后&#xff0c;您将能够通过HTTPS加密通道安全访问To…

ffmpeg教程及加速视频转码

ffmpeg教程及加速视频转码 1、ffmpeg简介&#xff1a; ffmpeg来自MPEG视频编码标准。 是一套可以用来记录&#xff0c;转换数字音频、视频&#xff0c;并能将其转化为流的开源计算机程序。 可以轻易的实现多种视频格式之间的相互转换。 2、基础知识&#xff1a; 容器、文件…

FDM3D打印系列——创想三维打印机卡料修复后续处理

大家好&#xff0c;我是阿赵。   之前我的创想三维Sermoon v1打印机卡料了&#xff0c;我自己拆开打印头组件&#xff0c;把卡料的地方修复了。   但问题并没有彻底的解决。在后续打印之中&#xff0c;还是经常出现卡料。有些需要打印实际个小时的模型&#xff0c;在打印了…

基于Material Design风格开源的Avalonia UI控件库

前言 今天大姚给大家分享一款基于Material Design风格开源、免费&#xff08;MIT License&#xff09;的Avalonia UI控件库&#xff1a;Material.Avalonia。 当前项目还处于alpha阶段。 Avalonia介绍 Avalonia是一个强大的框架&#xff0c;使开发人员能够使用.NET创建跨平台应…

内网穿透的应用-如何使用跨平台终端Tabby结合内网穿透工具异地远程ssh访问Ubuntu系统

文章目录 前言1. Tabby下载安装2. Tabby相关配置3. Tabby简单操作4. ssh连接Linux4.1 ubuntu系统安装ssh4.2 Tabby远程ssh连接ubuntu 5. 安装内网穿透工具5.1 创建公网地址5.2 使用公网地址远程ssh连接 6. 配置固定公网地址 前言 今天和大家分享一下如何在Windows系统使用Tabb…

Trimming项目完整流程

Trimming项目完整流程 FsmStates状态机 public enum FsmStates {// 初始状态&#xff0c;FSM 启动后的第一个状态Initial,// 等待序列化过程控制器&#xff08;SPS&#xff09;启动的状态// 在此状态下&#xff0c;FSM 等待外部系统或设备准备就绪WaitOnSPSStart,// 加载数据库…

【使用python实现多目标批量ping】附案例

以下为使用 Python 实现批量 ping 的多种方法及代码示例&#xff1a; 方法一&#xff1a; import subprocessfilepath E:\\Python\\tools\\AutoMatic\\hosts.txt with open(filepath, r) as f:hosts f.readlines()for host in hosts:result subprocess.check_output((ping…