题解 P1248 【加工生产调度】

· · 题解

第一吃螃蟹的感觉真好！

第一篇题解 by ljc20020730

n个作业要在由两台机器M1和M2组成的流水线上完成加工．每个作业i必须先在M1上然后在M2上加工，时间分别为ai和bi。

确定这n个作业的加工顺序，使得从第一个任务开始在M1上加工到最后一个任务在M2上加工完成的总时间尽量小。

直观上，最优调度一定让M1没有空闲，M2的空闲时间尽量少。

算法:①使用数组f1[j] 存放a[i]<b[i]的作业；

②使用数组f2[k] 存放a[i]>=b[i]的作业;

③对f1[j]根据a[j]进行升序排列;

④对f2[k]根据b[k]进行降序排列;

⑤遍历两个数组，依次求时间:取两个机器运行时间的较大值作为作业用时。

程序易于实现，时间O(nlogn)，关键在于正确性证明。