NOIP 普及组初赛 · NOIP 2016 普及组初赛试题 第 19 题

周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜 10 分钟，然后切菜 10 分钟，最后炒菜 10 分钟。那么做一道菜需要 30 分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要（ ）分钟。

这道题本质是流水线调度。拿到题先画甘特图，把小明、爸爸、妈妈的工序错开排，只要保证同一人不同时做同一工序、不同工序能并行，就能看出最优解。

学生最容易掉进两个坑：一是死板理解‘不同步骤不能同时’，以为必须等上一道菜全部做完才能碰下一道，结果算成90分钟；二是把流水线公式套错，比如误以为总时间是30×3=90，或者忘了n+m-1这个减1的修正项，导致选错B或D。其实核心就是‘同一人串行、不同人并行’，画图最直观。

流水线调度

考点与概念

本题考查的是流水线调度（Pipeline Scheduling）：多任务、多阶段、多资源协同的最优排序问题。约束很明确——同一人不能同时做两道菜的同一工序，但不同人可以同时工作。这类问题在信息学竞赛里常用来模拟真实生产场景，比如工厂装配线、厨房做菜等。