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

devtools/2024/9/30 0:24:24/

一、题目

        第 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.ppmy.cn/devtools/104939.html

相关文章

单窗口IP代理设置指南:轻松搞定

在现代互联网生活中&#xff0c;IP代理已经成为了许多人日常上网的必备工具。单窗口IP代理是一种非常实用的代理方式&#xff0c;它允许你在同一个浏览器中为不同的窗口设置不同的IP地址&#xff0c;从而更好地保护隐私和实现多任务处理。今天&#xff0c;我们就来详细讲解一下…

AI引领,驱动未来:零售企业的新质生产力革命

在这个快节奏的零售世界里&#xff0c;每一天都充满了变数。但你是否想象过&#xff0c;当AI&#xff08;人工智能&#xff09;、驱动技术、商品计划软件以及新质生产力携手并进时&#xff0c;零售企业将如何焕发新生&#xff0c;轻松应对挑战&#xff0c;引领行业潮流&#xf…

数字芯片中I/O单元及电源domain布局中SIPI的考虑

芯片设计的物理实施过程通常也简称为布局布线&#xff08;P&R&#xff0c;Place-and-Route&#xff09;&#xff0c;布局一般被分为布局规划&#xff08;Floorplan&#xff09;和标准单元摆放&#xff08;Place&#xff09;两个过程。而其中的布局规划是芯片后端物理实现过…

数学基础 -- 线性代数之酉矩阵

酉矩阵&#xff08;Unitary Matrix&#xff09; 酉矩阵是线性代数中一种重要的矩阵类型&#xff0c;特别在量子力学和信号处理等领域有广泛的应用。以下是酉矩阵的定义、性质以及使用和计算的例子。 1. 定义 酉矩阵是一个复矩阵 U U U &#xff0c;满足以下条件&#xff1a…

如何把钓鱼邮件“拒之门外”?试试U-Mail邮件安全网关

在当今信息化时代&#xff0c;互联网的发展使得人与人之间的沟通变得更加便捷和频繁&#xff0c;通过互联网&#xff0c;人们可以随时与远在他处的朋友或者业务伙伴进行交流。同时也给不法之徒利用互联网进行欺诈和违法犯罪提供了可乘之机。钓鱼邮件就是不法之徒利用网络实施不…

OceanbaseV4模拟题解析

使用 Docker 部署的 OceanBase 可以作为MetaDB&#xff0c;供OceanBase相关产品作为元数据数据库来使用。以下哪类产品需要MetaDB?&#xff08;AD&#xff09; ​ A OCP ​ B OBProxy ​ C OAT ​ D OMS MetaDB&#xff1a;基于容器部署的 OceanBase 数据库服务&#xff0c;可…

uniapp二维码生成

uniapp二维码生成 参考文档依赖引入代码html部分生成代码&#xff08;vue3 hook&#xff09;使用 参考文档 【博主&#xff1a;ChoneyLove】uniapp中生成二维码及解决微信小程序端问题总结 依赖引入 npm i uqrcodejs代码 html部分 <canvas type"2d" id"…

了解ceph scrub deep-scrub

目的 了解 ceph scrub, deep-scrub 作用了解 ceph scrub, deep-scrub 相关配置参考告警 $ ceph -scluster:id: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxhealth: HEALTH_WARN434 pgs not deep-scrubbed in time <------ warningservices:mon: 6 daemons, quorum c…