每个工件的每个工序称为一个操作#xff0c;…[NOIP2006

提高组]

道工序每道工序都在不同的指定的机器上完成。

每个工件的每道工序都有指定的加工时间。

j-k

道工序的这个操作。

在本题中我们还给定对于各操作的一个安排顺序。

例如当

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

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

还要注意“安排顺序”只要求按照给定的顺序安排每个操作。

不一定是各机器上的实际操作顺序。

在具体实施时有可能排在后面的某个操作比前面的某个操作先完成。

例如取

当一个操作插入到某台机器的某个空档时机器上最后的尚未安排操作的部分也可以看作一个空档可以靠前插入也可以靠后或居中插入。

为了使问题简单一些我们约定在保证约束条件

2的条件下尽量靠前插入。

并且我们还约定如果有多个空档可以插入就在保证约束条件

2的条件下插入到最前面的一个空档。

于是在这些约定下上例中的方案一是正确的而方案二是不正确的。

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

输入格式

当处理这个问题时我们可以将其类比成一个工厂里的任务分配问题。

下面是一个小学生都能理解的解题思路附带一些简单的代码解释。

1.明确问题

我们有很多台机器和很多个任务每个任务都有几个步骤每个步骤都需要在某个机器上完成并且需要花一些时间。

2.获取机器和任务数量

对于每个任务我们需要知道每个步骤应该在哪台机器上完成以及需要花多少时间。

struct

针对每个任务和每个步骤读取它应该在哪台机器上完成以及需要花多少时间。

for

对于每个任务步骤我们会找到合适的时间段然后更新机器的时间线并记录任务的完成时间。

这段代码比较难以理解所以我把他再次分为几点

int

最终答案所有任务都完成的时间点6.1这些数组用于存储我们模拟中需要的信息。

machineTimeline

for

jobList[i];jobStep[currentJob];int

currentMachineId

jobs[currentJob][jobStep[currentJob]].machineId;int

currentTimeCost

jobs[currentJob][jobStep[currentJob]].timeCost;int

0;for

(machineTimeline[currentMachineId][j]

{s;}

{machineTimeline[currentMachineId][k]

1;}if

是当前任务步骤对应的任务编号。

我们递增jobStep[currentJob]表示当前任务已完成的步骤数。

然后我们获取当前步骤需要在哪台机器上执行以及需要多少时间。

我们使用

s来记录在机器上找到的可用时间段的长度。

我们从上次这个任务完成的时间lastJobTime[currentJob]的下一个时间点开始查找。

我们检查

machineTimeline[currentMachineId][j]如果等于

s否则表示机器正在被占用我们将

的值达到当前步骤所需的时间时说明我们找到了一个满足条件的时间段。

我们将从

currentTimeCost

lastJobTime[currentJob]表示当前任务上一次完成的时间。

在这段代码中s

是用来计算连续空闲时间段的计数器。

当我们需要找到一个连续时间段足够容纳当前步骤所需的时间时我们使用

在循环中我们逐步递增

j检查机器时间线上的每个时间点。

如machineTimeline[currentMachineId][j]

0那么我们递增

currentTimeCost说明我们找到了一个足够长的连续空闲时间段可以在机器上执行当前任务步骤。

然后我们会将这个时间段标记为机器被占用并更新相应的时间和计数器。

在这里充当了一个计数器帮助我们在机器时间线上找到足够长的连续空闲时间段以满足当前任务步骤的时间要求。

最后附上完整代码

jobList[i];jobStep[currentJob];int

currentMachineId

jobs[currentJob][jobStep[currentJob]].machineId;int

currentTimeCost

jobs[currentJob][jobStep[currentJob]].timeCost;int

0;//

(machineTimeline[currentMachineId][j]

{s;}

{machineTimeline[currentMachineId][k]

1;}//

更新当前任务的上次完成时间lastJobTime[currentJob]

j;break;}}}//