头歌实训作业 算法设计与分析-贪心算法(第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 个作业(编号为1~n)要在由两台机器 M 1和 M 2 组成的流水线上完成加工。每个作业加工的顺序都是先在 M 1上加工,然后在 M 2 上加工。 M 1 和 M 2 加工作业 i 所需的时间分别为 a i 和 b i(1≤i≤n&am…...
Hadoop•搭建完全分布式集群
听说这里是目录哦 一、安装Hadoop🥕二、配置Hadoop系统环境变量🥮三、验证Hadoop系统环境变量是否配置成功🧁四、修改Hadoop配置文件🍭五、分发Hadoop安装目录🧋六、分发系统环境变量文件🍨七、格式化HDFS文…...
SQL-leetcode—1141. 查询近30天活跃用户数
1141. 查询近30天活跃用户数 表:Activity ---------------------- | Column Name | Type | ---------------------- | user_id | int | | session_id | int | | activity_date | date | | activity_type | enum | ---------------------- 该表没有包含重复数据。 …...
总结与展望,龙蜥社区第 30 次运营委员会会议线上召开
2025 年 1 月 20 日,龙蜥社区召开了第 30 次运营委员会线上会议,来自 24 家理事单位的 22 位委员及委员代表出席,本次会议由运营委员凝思软件李晨斌主持。会上总结和回顾了龙蜥社区 1 月运营发展情况,同步了龙蜥社区 3 大运营目标…...
idea对jar包内容进行反编译
1.先安装一下这个插件java Bytecode Decompiler 2.找到这个插件的路径,在idea的plugins下面的lib文件夹内:java-decompiler.jar。下面是我自己本地的插件路径,以作参考: D:\dev\utils\idea\IntelliJ IDEA 2020.1.3\plugins\java-d…...
c++----------------------多态
1.多态 1.1多态的概念 多态(polymorphism)的概念:通俗来说,就是多种形态。多态分为编译时多态(静态多态)和运⾏时多 态(动态多态),这⾥我们重点讲运⾏时多态,编译时多态(静态多态)和运⾏时多态(动态多态)。编译时 多态(静态多态)…...
C语言 指针_野指针 指针运算
野指针: 概念:野指针就是指针指向的位置是不可知的(随机的、不正确的、没有明确限制的) 指针非法访问: int main() {int* p;//p没有初始化,就意味着没有明确的指向//一个局部变量不初始化,放…...
【JavaEE进阶】Spring留言板实现
目录 🎍预期结果 🍀前端代码 🎄约定前后端交互接口 🚩需求分析 🚩接口定义 🌳实现服务器端代码 🚩lombok介绍 🚩代码实现 🌴运行测试 🎄前端代码实…...
第25篇 基于ARM A9处理器用C语言实现中断<一>
Q:怎样理解基于ARM A9处理器用C语言实现中断的过程呢? A:同样以一段使用C语言实现中断的主程序为例介绍,和汇编语言实现中断一样这段代码也使用了定时器中断和按键中断。执行该主程序会在DE1-SoC的红色LED上显示流水灯…...
面向通感一体化的非均匀感知信号设计
文章目录 1 非均匀信号设计的背景分析1.1 基于OFDM波形的感知信号1.2 非均匀信号设计的必要性和可行性1.2 非均匀信号设计的必要性和可行性 3 通感一体化系统中的非均匀信号设计方法3.1 非均匀信号的设计流程(1)均匀感知信号设计(2࿰…...
修改docker共享内存shm-size
法1:在创建容器时增加共享内存大小 nvidia-docker run -it -p 10000:22 --name"zm" -v /home/zm:/data ufoym/deepo:all-cu101 /bin/bash --shm-size20G法2:修改正在运行的容器的共享内存设置 查看容器、共享内存 docker ps -a df -lh | gr…...
WIN11 UEFI漏洞被发现, 可以绕过安全启动机制
近日,一个新的UEFI漏洞被发现,可通过多个系统恢复工具传播,微软已经正式将该漏洞标记为追踪编号“CVE-2024-7344”。根据报告的说明,该漏洞能让攻击者绕过安全启动机制,并部署对操作系统隐形的引导工具包。 据TomsH…...
网安加·百家讲坛 | 樊山:数据安全之威胁建模
作者简介:樊山,锦联世纪教育能源工业互联网数字安全CSM(新能源运维师)课程特聘培训讲师,哈尔滨工业大学(深圳)信飞合创数据合规联合实验室特聘专家,武汉赛博网络安全人才研究中心资深专家;近24年…...
jQuery阶段总结(二维表+思维导图)
引言 经过23天的学习,期间有期末考试,有放假等插曲。本来应该在学校里学习,但是特殊原因,让回家了。但是在家学习的过程,虽然在学,很让我感觉到不一样。但是效果始终还是差点的,本来17、18号左右…...
【LLM】RedisSearch 向量相似性搜索在 SpringBoot 中的实现
整理不易,请不要吝啬你的赞和收藏。 1. 前言 写这篇文章挺不容易的,网络上对于 SpringBoot 实现 Redis 向量相似性搜索的文章总体来说篇幅较少,并且这些文章很多都写得很粗糙,或者不是我想要的实现方式,所以我不得不阅…...
如何为64位LabVIEW配置正确的驱动程序
在安装 64位 LabVIEW 后,确保驱动程序正确配置是关键。如果您首先安装了 32位 LabVIEW 和相关驱动,然后安装了 64位 LabVIEW,需要确保为 64位 LabVIEW 安装和配置适当的驱动程序,才能正常访问硬件设备。以下是详细步骤:…...
Redis(5,jedis和spring)
在前面的学习中,只是学习了各种redis的操作,都是在redis命令行客户端操作的,手动执行的,更多的时候就是使用redis的api(),进一步操作redis程序。 在java中实现的redis客户端有很多,…...
Git 小白入门教程
🎯 这篇文章详细介绍了版本控制的重要性,特别是通过Git实现的分布式版本控制相对于SVN集中式控制的优势。文章首先解释了版本控制的基本概念,强调了在文档或项目多版本迭代中备份与恢复任意版本的能力。接着,重点阐述了Git的历史背…...
Python从0到100(八十五):神经网络与迁移学习在猫狗分类中的应用
在人工智能的浩瀚宇宙中,深度学习犹如一颗璀璨的星辰,引领着机器学习和计算机视觉领域的前沿探索。而神经网络,作为深度学习的核心架构,更是以其强大的数据建模能力,成为解决复杂问题的重要工具。今天,我们…...
代码随想录刷题day14(2)|(链表篇)02.07. 链表相交(疑点)
目录 一、链表理论基础 二、链表相交求解思路 三、相关算法题目 四、疑点 一、链表理论基础 代码随想录 二、链表相交求解思路 链表相交时,是结点的位置,也就是指针相同,不是结点的数值相同; 思路:定义两个指针…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
