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

头歌实训作业 算法设计与分析-贪心算法(第5关:求解流水作业调度问题)

问题描述


有 n 个作业(编号为1~n)要在由两台机器 M 1和 M 2 组成的流水线上完成加工。每个作业加工的顺序都是先在 M 1​上加工,然后在 M 2  上加工。 M 1 和 M 2  加工作业 i 所需的时间分别为 a i 和 b i(1≤i≤n)。
流水作业调度问题要求确定这 n 个作业的最优加工顺序,使得从第一个作业在机器 M 1 上开始加工,到最后一个作业在机器 M 2 上加工完成所需的时间最少。可以假定任何作业一旦开始加工,就不允许被中断,直到该作业被完成,即非优先调度。

测试说明


输入格式:
第一行输入作业数 n,接着的 n 行分别为在 M 1和M 2 加工各作业所需的时间。

输出格式:
输出最优调度方案(时间最少)所需的时间。

输入样例1:
4
5 6  作业1在M1上执行时间为5,在M2上执行时间为6
12 2
4 14
8 7

输出样例1:
33

输出样例1解释:
总时间=33
调度方案
第1步执行作业3
第2步执行作业1
第3步执行作业4
第4步执行作业2

注意算法的时间复杂度优化,避免评测超时。

补充代码: 

 #include<bits/stdc++.h>using namespace std;typedef long long ll;const int N =1010;struct Node{ll t, idx;}Nodes[N];int a[N],b[N];bool cmp(Node & a , Node & b){return a.t< b.t;}int ans[N];void solve(){int n;cin >> n;for(int i=1;i<=n;i++){Nodes[i].idx = i;cin >> a[i] >> b[i];if(a[i] <= b[i]){Nodes[i].t = a[i];}else{Nodes[i].t = b[i];}}sort(Nodes + 1, Nodes +1 +n,cmp);int f1 =0,f2=0;int l =1,r=n;for(int i=1;i<=n;i++){if(Nodes[i].t == a[Nodes[i].idx]){ans[l++] = Nodes[i].idx;}else{ans[r --] = Nodes[i].idx;}}for(int i=1;i<=n;i++){int id = ans[i];f1 += a[id];f2 = max(f1,f2) + b[id];}cout << f2 << endl;}int main () {solve();return 0;}

 

相关文章:

头歌实训作业 算法设计与分析-贪心算法(第5关:求解流水作业调度问题)

问题描述 有 n 个作业&#xff08;编号为1&#xff5e;n&#xff09;要在由两台机器 M 1和 M 2 组成的流水线上完成加工。每个作业加工的顺序都是先在 M 1​上加工&#xff0c;然后在 M 2 上加工。 M 1 和 M 2 加工作业 i 所需的时间分别为 a i 和 b i&#xff08;1≤i≤n&am…...

Hadoop•搭建完全分布式集群

听说这里是目录哦 一、安装Hadoop&#x1f955;二、配置Hadoop系统环境变量&#x1f96e;三、验证Hadoop系统环境变量是否配置成功&#x1f9c1;四、修改Hadoop配置文件&#x1f36d;五、分发Hadoop安装目录&#x1f9cb;六、分发系统环境变量文件&#x1f368;七、格式化HDFS文…...

SQL-leetcode—1141. 查询近30天活跃用户数

1141. 查询近30天活跃用户数 表&#xff1a;Activity ---------------------- | Column Name | Type | ---------------------- | user_id | int | | session_id | int | | activity_date | date | | activity_type | enum | ---------------------- 该表没有包含重复数据。 …...

总结与展望,龙蜥社区第 30 次运营委员会会议线上召开

2025 年 1 月 20 日&#xff0c;龙蜥社区召开了第 30 次运营委员会线上会议&#xff0c;来自 24 家理事单位的 22 位委员及委员代表出席&#xff0c;本次会议由运营委员凝思软件李晨斌主持。会上总结和回顾了龙蜥社区 1 月运营发展情况&#xff0c;同步了龙蜥社区 3 大运营目标…...

idea对jar包内容进行反编译

1.先安装一下这个插件java Bytecode Decompiler 2.找到这个插件的路径&#xff0c;在idea的plugins下面的lib文件夹内&#xff1a;java-decompiler.jar。下面是我自己本地的插件路径&#xff0c;以作参考&#xff1a; D:\dev\utils\idea\IntelliJ IDEA 2020.1.3\plugins\java-d…...

c++----------------------多态

1.多态 1.1多态的概念 多态(polymorphism)的概念&#xff1a;通俗来说&#xff0c;就是多种形态。多态分为编译时多态(静态多态)和运⾏时多 态(动态多态)&#xff0c;这⾥我们重点讲运⾏时多态&#xff0c;编译时多态(静态多态)和运⾏时多态(动态多态)。编译时 多态(静态多态)…...

C语言 指针_野指针 指针运算

野指针&#xff1a; 概念&#xff1a;野指针就是指针指向的位置是不可知的&#xff08;随机的、不正确的、没有明确限制的&#xff09; 指针非法访问&#xff1a; int main() {int* p;//p没有初始化&#xff0c;就意味着没有明确的指向//一个局部变量不初始化&#xff0c;放…...

【JavaEE进阶】Spring留言板实现

目录 &#x1f38d;预期结果 &#x1f340;前端代码 &#x1f384;约定前后端交互接口 &#x1f6a9;需求分析 &#x1f6a9;接口定义 &#x1f333;实现服务器端代码 &#x1f6a9;lombok介绍 &#x1f6a9;代码实现 &#x1f334;运行测试 &#x1f384;前端代码实…...

第25篇 基于ARM A9处理器用C语言实现中断<一>

Q&#xff1a;怎样理解基于ARM A9处理器用C语言实现中断的过程呢&#xff1f; A&#xff1a;同样以一段使用C语言实现中断的主程序为例介绍&#xff0c;和汇编语言实现中断一样这段代码也使用了定时器中断和按键中断。执行该主程序会在DE1-SoC的红色LED上显示流水灯&#xf…...

面向通感一体化的非均匀感知信号设计

文章目录 1 非均匀信号设计的背景分析1.1 基于OFDM波形的感知信号1.2 非均匀信号设计的必要性和可行性1.2 非均匀信号设计的必要性和可行性 3 通感一体化系统中的非均匀信号设计方法3.1 非均匀信号的设计流程&#xff08;1&#xff09;均匀感知信号设计&#xff08;2&#xff0…...

修改docker共享内存shm-size

法1&#xff1a;在创建容器时增加共享内存大小 nvidia-docker run -it -p 10000:22 --name"zm" -v /home/zm:/data ufoym/deepo:all-cu101 /bin/bash --shm-size20G法2&#xff1a;修改正在运行的容器的共享内存设置 查看容器、共享内存 docker ps -a df -lh | gr…...

WIN11 UEFI漏洞被发现, 可以绕过安全启动机制

近日&#xff0c;一个新的UEFI漏洞被发现&#xff0c;可通过多个系统恢复工具传播&#xff0c;微软已经正式将该漏洞标记为追踪编号“CVE-2024-7344”。根据报告的说明&#xff0c;该漏洞能让攻击者绕过安全启动机制&#xff0c;并部署对操作系统隐形的引导工具包。 据TomsH…...

网安加·百家讲坛 | 樊山:数据安全之威胁建模

作者简介&#xff1a;樊山&#xff0c;锦联世纪教育能源工业互联网数字安全CSM(新能源运维师)课程特聘培训讲师&#xff0c;哈尔滨工业大学&#xff08;深圳&#xff09;信飞合创数据合规联合实验室特聘专家&#xff0c;武汉赛博网络安全人才研究中心资深专家&#xff1b;近24年…...

jQuery阶段总结(二维表+思维导图)

引言 经过23天的学习&#xff0c;期间有期末考试&#xff0c;有放假等插曲。本来应该在学校里学习&#xff0c;但是特殊原因&#xff0c;让回家了。但是在家学习的过程&#xff0c;虽然在学&#xff0c;很让我感觉到不一样。但是效果始终还是差点的&#xff0c;本来17、18号左右…...

【LLM】RedisSearch 向量相似性搜索在 SpringBoot 中的实现

整理不易&#xff0c;请不要吝啬你的赞和收藏。 1. 前言 写这篇文章挺不容易的&#xff0c;网络上对于 SpringBoot 实现 Redis 向量相似性搜索的文章总体来说篇幅较少&#xff0c;并且这些文章很多都写得很粗糙&#xff0c;或者不是我想要的实现方式&#xff0c;所以我不得不阅…...

如何为64位LabVIEW配置正确的驱动程序

在安装 64位 LabVIEW 后&#xff0c;确保驱动程序正确配置是关键。如果您首先安装了 32位 LabVIEW 和相关驱动&#xff0c;然后安装了 64位 LabVIEW&#xff0c;需要确保为 64位 LabVIEW 安装和配置适当的驱动程序&#xff0c;才能正常访问硬件设备。以下是详细步骤&#xff1a…...

Redis(5,jedis和spring)

在前面的学习中&#xff0c;只是学习了各种redis的操作&#xff0c;都是在redis命令行客户端操作的&#xff0c;手动执行的&#xff0c;更多的时候就是使用redis的api&#xff08;&#xff09;&#xff0c;进一步操作redis程序。 在java中实现的redis客户端有很多&#xff0c;…...

Git 小白入门教程

&#x1f3af; 这篇文章详细介绍了版本控制的重要性&#xff0c;特别是通过Git实现的分布式版本控制相对于SVN集中式控制的优势。文章首先解释了版本控制的基本概念&#xff0c;强调了在文档或项目多版本迭代中备份与恢复任意版本的能力。接着&#xff0c;重点阐述了Git的历史背…...

Python从0到100(八十五):神经网络与迁移学习在猫狗分类中的应用

在人工智能的浩瀚宇宙中&#xff0c;深度学习犹如一颗璀璨的星辰&#xff0c;引领着机器学习和计算机视觉领域的前沿探索。而神经网络&#xff0c;作为深度学习的核心架构&#xff0c;更是以其强大的数据建模能力&#xff0c;成为解决复杂问题的重要工具。今天&#xff0c;我们…...

代码随想录刷题day14(2)|(链表篇)02.07. 链表相交(疑点)

目录 一、链表理论基础 二、链表相交求解思路 三、相关算法题目 四、疑点 一、链表理论基础 代码随想录 二、链表相交求解思路 链表相交时&#xff0c;是结点的位置&#xff0c;也就是指针相同&#xff0c;不是结点的数值相同&#xff1b; 思路&#xff1a;定义两个指针…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...