当前位置: 首页 > article >正文

【数据结构-堆】力扣3296. 移山所需的最少秒数

给你一个整数 mountainHeight 表示山的高度。

同时给你一个整数数组 workerTimes,表示工人们的工作时间(单位:秒)。

工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :

山的高度降低 x,需要花费 workerTimes[i] + workerTimes[i] * 2 + … + workerTimes[i] * x 秒。例如:
山的高度降低 1,需要 workerTimes[i] 秒。
山的高度降低 2,需要 workerTimes[i] + workerTimes[i] * 2 秒,依此类推。
返回一个整数,表示工人们使山的高度降低到 0 所需的 最少 秒数。

示例 1:
输入: mountainHeight = 4, workerTimes = [2,1,1]

输出: 3

解释:

将山的高度降低到 0 的一种方式是:

工人 0 将高度降低 1,花费 workerTimes[0] = 2 秒。
工人 1 将高度降低 2,花费 workerTimes[1] + workerTimes[1] * 2 = 3 秒。
工人 2 将高度降低 1,花费 workerTimes[2] = 1 秒。
因为工人同时工作,所需的最少时间为 max(2, 3, 1) = 3 秒。

示例 2:
输入: mountainHeight = 10, workerTimes = [3,2,2,4]

输出: 12

解释:

工人 0 将高度降低 2,花费 workerTimes[0] + workerTimes[0] * 2 = 9 秒。
工人 1 将高度降低 3,花费 workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12 秒。
工人 2 将高度降低 3,花费 workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12 秒。
工人 3 将高度降低 2,花费 workerTimes[3] + workerTimes[3] * 2 = 12 秒。
所需的最少时间为 max(9, 12, 12, 12) = 12 秒。

示例 3:
输入: mountainHeight = 5, workerTimes = [1]

输出: 15

解释:

这个示例中只有一个工人,所以答案是 workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15 秒。

最小堆

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> q;

        for(int i = 0; i < workerTimes.size(); i++){
            q.push({(long long)workerTimes[i], i, 1});
        }

        long long ans = 0;
        for(int i = 0; i < mountainHeight; i++){
            auto [Time, idx, cnt] = q.top();
            q.pop();
            ans = max(ans, Time);
            int nextCnt = cnt + 1;
            long long nextTime = Time + (long long)workerTimes[idx] * nextCnt;
            q.push({nextTime, idx, nextCnt});
        }

        return ans;
    }
};

时间复杂度:O(mountainHeightlogn),其中 n 是 workerTimes 的长度。
空间复杂度:O(n)。

这道题我们要注意的是工人是同时工作的,我们要求他最少时间,那么也就是说我们要让干最久的工人的时间尽可能少。首先我们由题目可以知道,假如我们把移山的任务分成每个单位,那么我们可以由工人的workerTimes和他操作的次数来判断他完成这个任务所需要的时间。我们定义一个三元组tuple<long long, int, int>,分别对应工作累积时间、工人序号、操作的对应次数。我们建立一个最小堆q来储存工人下一次移除单位后的累积时间是多少,然后我们每次选择q的队头也就是完成下一单位后累计工作时间最少的工人。并且我们定义一个变量ans来记录最大的累计工作时间,最后ans中储存的就是完成移山所需得到最少秒数。


http://www.kler.cn/a/472507.html

相关文章:

  • C++语言的面向对象编程
  • SSM-SpringMVC-请求响应、REST、JSON
  • uniapp vue2版本如何设置i18n
  • STM32-笔记35-DMA(直接存储器访问)
  • 嵌入式中QT实现文本与线程控制方法
  • 前端数据模拟器 mockjs 和 fakerjs
  • 第P5周-Pytorch实现运动鞋品牌识别
  • 英伟达开启“AI 代理时代” | AI日报0108
  • 新手入门 React .tsx 项目:从零到实战
  • Servlet 和 Spring MVC:区别与联系
  • 51c自动驾驶~合集45
  • h264之多视点mvc编码及解码过程(JMVC平台举例)
  • CSS语言的数据结构
  • 条款47:请使用 traits classes 表现类型信息(Use traits classes for information about types)
  • 【利用 Unity + Mirror 网络框架、Node.js 后端和 MySQL 数据库】
  • c#委托和事件
  • 30、论文阅读:基于小波的傅里叶信息交互与频率扩散调整的水下图像恢复
  • 大数据技术(九)—— HBase优化
  • 【QT-QTableView实现鼠标悬浮(hover)行高亮显示+并设置表格样式】
  • SpringBoot中的设计模
  • 03、Docker学习,理论知识,第三天--DockerFile
  • linuxCNC(六)配置LinuxCNC完成伺服控制
  • pytorch torch.arange函数介绍
  • 鸿蒙中调整应用内文字大小
  • android的显式隐式intent
  • Taro+react 开发第一节创建 带有redux状态管理的项目