P1065 [NOIP2006 提高组] 作业调度方案题目

2024-01-26 04:12

本文主要是介绍P1065 [NOIP2006 提高组] 作业调度方案题目,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

我们现在要利用m台机器加工n个工件,每个工件都有m道工序,每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。

每个工件的每个工序称为一个操作,我们用记号j-k表示一个操作,其中j为1到n中的某个数字,为工件号;k为1到m中的某个数字,为工序号,例如2-4表示第2个工件第4道工序的这个操作。在本题中,我们还给定对于各操作的一个安排顺序。

例如,当n=3,m=2时,1-1,1-2,2-1,3-1,3-2,2-2就是一个给定的安排顺序,即先安排第1个工件的第1个工序,再安排第1个工件的第2个工序,然后再安排第2个工件的第1个工序,等等。

一方面,每个操作的安排都要满足以下的两个约束条件。

  1. 对同一个工件,每道工序必须在它前面的工序完成后才能开始;

  2. 同一时刻每一台机器至多只能加工一个工件。

另一方面,在安排后面的操作时,不能改动前面已安排的操作的工作状态。

由于同一工件都是按工序的顺序安排的,因此,只按原顺序给出工件号,仍可得到同样的安排顺序,于是,在输入数据中,我们将这个安排顺序简写为1 1 2 3 3 2

还要注意,“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时,有可能排在后面的某个操作比前面的某个操作先完成。

例如,取n=3,m=2,已知数据如下(机器号/加工时间):

工件号工序 1工序 2
11/32/2
21/22/5
32/21/4

则对于安排顺序1 1 2 3 3 2,下图中的两个实施方案都是正确的。但所需要的总时间分别是10与12。

方案1,用时10:

时间12345678910
机器1执行工序1-11-11-12-12-13-23-23-23-2
机器2执行工序3-13-11-21-22-22-22-22-22-2

方案2,用时12:

时间123456789101112
机器1执行工序1-11-11-12-12-13-23-23-23-2
机器2执行工序1-21-23-13-12-22-22-22-22-2

当一个操作插入到某台机器的某个空档时(机器上最后的尚未安排操作的部分也可以看作一个空档),可以靠前插入,也可以靠后或居中插入。为了使问题简单一些,我们约定:在保证约束条件(1.)(2.) 的条件下,尽量靠前插入。并且,我们还约定,如果有多个空档可以插入,就在保证约束条件(1.)(2.)的条件下,插入到最前面的一个空档。于是,在这些约定下,上例中的方案一是正确的,而方案二是不正确的。

显然,在这些约定下,对于给定的安排顺序,符合该安排顺序的实施方案是唯一的,请你计算出该方案完成全部任务所需的总时间。

输入输出格式

输入格式

第1行为两个正整数m, n,用一个空格隔开, 其中m(<20) 表示机器数,n(<20)表示工件数。

第2行:m×n个用空格隔开的数,为给定的安排顺序。

接下来的2n行,每行都是用空格隔开的m个正整数,每个数不超过20。

其中前n行依次表示每个工件的每个工序所使用的机器号,第1个数为第1个工序的机器号,第2个数为第2个工序机器号,等等。

后n行依次表示每个工件的每个工序的加工时间。

可以保证,以上各数据都是正确的,不必检验。

输出格式

1 个正整数,为最少的加工时间。

输入输出样例

输入样例

2 3
1 1 2 3 3 2
1 2 
1 2 
2 1
3 2 
2 5 
2 4

输出样例

10

解析

题目已经给出了安排好的工序,而每个工序需要在几号机上完成以及每个工序的时间也给了出来,我们要做的就是合理安排机器的工作,让总的加工时间最短。

按照题意的约定,最短方案有且只有一种,而且不必判断输入的合法性。

我们可以把机器想成若干个「时间线」,在这条时间线上去安排工作。

那么明显的,每个时间段对应的机器就只有俩状态:1.我在干活     2.我闲着呢

而每一个工件也有自己的加工要求,对于每个工件的工序,总应该先完成小号工序再完成大号工序,也就是必须顺着编号来。

每台机器只能在某时刻进行一种工作,并且后面的安排不能把前面的安排改动掉。

模拟的思想便是从左到右无限扫描整个时间线,然后去尝试插空。

有三个辅助数组,第一个是cnt_now_work_step,它表示当前取到工件的工序数。根据之前输入的workline,每个数都代表一个安排的工序,这个数组就是用来方便后面处理工序的。第二个是lasttime,它代表某个工件出现的最晚的时间(点),它可以用来方便我们扫描时间线,因为每一个工件必须要完全完成上一道工序后才能接着继续下一道工序。第三个是二维bool数组timeline,它代表某一台机器在某一个时间(点)上是不是正在干活。

有了这三个辅助数组,我们就可以开始按照模拟的思路写代码了。

我们取当前工件nowitem[i],让cnt_now_work_step[nowitem]++,即代表这个工件的工序+1,用nownumber记录当前工件在当前工序时位于哪一台机器,costtime表示做完这道工序应该花费的时间,lasttime[nowitem]+1便是我们扫描时间线的开端,注意lasttime记录的是时间点。这个for没有终止条件,因为时间轴可能会无穷远。

接下来是关键,判断从这个时间点到干完这道工序,机器有没有空,如果机器表示“我闲着呢”,那么就把这道工序安排给机器的这个时间段,更新timeline和lasttime(lasttime[nowitem] = time + costtime - 1,干完活之后这个工件出现的最晚的时间点应该是这道新工序做完的那一刻),然后更新操作立即break掉,继续扫描时间线。如果机器表示“这个时间段我在干其他活”,那这个任务就不能放在这一段,时间线继续扫描。

这个判断这里用一个函数来实现,它传入起始时间点和终止时间点和工件编号,然后去判断它的timeline。循环完所有的工件,整个的时间轴也就确定了。最后去寻找ans,ans应该等于值最大的那个lasttime(即这个工件最后才做完)。输出ans即可。

代码

#include<iostream>
#define maxn 100
using namespace std;
int n,m;//定义工件数和机器数 
int ans = 0;//最后输出的结果 
int worklist[maxn * maxn];
int worknumber[maxn][maxn];
int worktime[maxn][maxn];
int cnt_now_work_step[maxn];
int lasttime[maxn];
bool timeline[maxn * maxn][maxn * maxn];//某一台机器在某一个时间(点)上是不是正在干活bool check_in_line(int begin_time_point,int end_time_length,int workid){for (int time = begin_time_point; time <= end_time_length;time++)if (timeline[workid][time])return false;return true;    
}//判断机器是不是空闲 int main(){cin >> m >> n;//输入机器数和工件数 for (int i=1;i<=n*m;i++){ cin >> worklist[i];//输入给定的安排顺序 } for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ cin >> worknumber[i][j];//每一工件每个工序的机器号 }} for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ cin >> worktime[i][j];//每个工件每个工序的加工时间 }} for (int i=1;i<=n*m;i++){int nowitem = worklist[i];//工件的安排顺序 cnt_now_work_step[nowitem]++;//当前取到工件的工序数int nownumber = worknumber[nowitem][cnt_now_work_step[nowitem]];//当前工件在当前工序时位于哪一台机器 int costtime = worktime[nowitem][cnt_now_work_step[nowitem]];//当前工件做完当前工序的加工时间 for (int time = lasttime[nowitem]+1;;time++)//扫描时间轴if (check_in_line(time,time+costtime-1,nownumber)){for (int marktime = time;marktime <= time+costtime-1;marktime++)timeline[nownumber][marktime] = true;lasttime[nowitem] = time + costtime - 1;break;}}for (int i=1;i<=n;i++)ans = max(ans,lasttime[i]);cout << ans << endl;return 0;
}

这篇关于P1065 [NOIP2006 提高组] 作业调度方案题目的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/645607

相关文章

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题:墙体两侧特征混淆误匹配,导致建图和定位偏差,表现为过门跳变、外月台走歪等 ·解决思路:预期的根治方案IGICP需要较长时间完成上线,先使用切分地图的工程化方案,即墙体两侧切分为不同地图,在某一侧只使用该侧地图进行定位 方案思路 切分原理:切分地图基于关键帧位置,而非点云。 理论基础:光照是直线的,一帧点云必定只能照射到墙的一侧,无法同时照到两侧实践考虑:关

作业提交过程之HDFSMapReduce

作业提交全过程详解 (1)作业提交 第1步:Client调用job.waitForCompletion方法,向整个集群提交MapReduce作业。 第2步:Client向RM申请一个作业id。 第3步:RM给Client返回该job资源的提交路径和作业id。 第4步:Client提交jar包、切片信息和配置文件到指定的资源提交路径。 第5步:Client提交完资源后,向RM申请运行MrAp

高效+灵活,万博智云全球发布AWS无代理跨云容灾方案!

摘要 近日,万博智云推出了基于AWS的无代理跨云容灾解决方案,并与拉丁美洲,中东,亚洲的合作伙伴面向全球开展了联合发布。这一方案以AWS应用环境为基础,将HyperBDR平台的高效、灵活和成本效益优势与无代理功能相结合,为全球企业带来实现了更便捷、经济的数据保护。 一、全球联合发布 9月2日,万博智云CEO Michael Wong在线上平台发布AWS无代理跨云容灾解决方案的阐述视频,介绍了

Android平台播放RTSP流的几种方案探究(VLC VS ExoPlayer VS SmartPlayer)

技术背景 好多开发者需要遴选Android平台RTSP直播播放器的时候,不知道如何选的好,本文针对常用的方案,做个大概的说明: 1. 使用VLC for Android VLC Media Player(VLC多媒体播放器),最初命名为VideoLAN客户端,是VideoLAN品牌产品,是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式,并支持DVD影音光盘,VCD影

搭建Kafka+zookeeper集群调度

前言 硬件环境 172.18.0.5        kafkazk1        Kafka+zookeeper                Kafka Broker集群 172.18.0.6        kafkazk2        Kafka+zookeeper                Kafka Broker集群 172.18.0.7        kafkazk3

JavaFX应用更新检测功能(在线自动更新方案)

JavaFX开发的桌面应用属于C端,一般来说需要版本检测和自动更新功能,这里记录一下一种版本检测和自动更新的方法。 1. 整体方案 JavaFX.应用版本检测、自动更新主要涉及一下步骤: 读取本地应用版本拉取远程版本并比较两个版本如果需要升级,那么拉取更新历史弹出升级控制窗口用户选择升级时,拉取升级包解压,重启应用用户选择忽略时,本地版本标志为忽略版本用户选择取消时,隐藏升级控制窗口 2.

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

如何选择SDR无线图传方案

在开源软件定义无线电(SDR)领域,有几个项目提供了无线图传的解决方案。以下是一些开源SDR无线图传方案: 1. **OpenHD**:这是一个远程高清数字图像传输的开源解决方案,它使用SDR技术来实现高清视频的无线传输。OpenHD项目提供了一个完整的工具链,包括发射器和接收器的硬件设计以及相应的软件。 2. **USRP(Universal Software Radio Periphera

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然