NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 13 题

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

这题考流水线调度。拿到题先想：三人分工明确，工序不能重叠但不同工序能并行。别被‘三道菜’吓住，试着把时间轴画出来，看什么时候能塞进下一道菜，就能立刻看出答案。

很多同学会惯性思维，觉得三道菜就得 30×3=90 分钟，或者只看到‘洗菜’能并行，忽略了切和炒的衔接。其实坑就坑在‘两道不同的菜的相同步骤不可以同时进行’这句话，它强制了工序串行，但不同工序可以手拉手并行。若没抓住这个约束，要么算出 90，要么错误地认为只要洗菜能重叠，后面也能无限重叠，导致误选更小的数字。

考点概念：流水线调度

这道题考查的是流水线调度（Pipeline Scheduling），也就是在资源受限的情况下，如何安排多个任务的最优执行顺序。核心在于理解：同一工序必须串行，不同工序可以并行。

命题视角与陷阱

命题人特意强调“两道不同的菜的相同步骤不可以同时进行”，就是为了排除那种“三个人同时洗三盘菜”的幻想。真实的坑在于：学生容易只盯着“洗菜”能并行，却忘了“切菜”和“炒菜”也有严格的先后顺序。如果没抓住这个约束，要么算出 90（串行），要么错误地认为只要洗菜能重叠，后面也能无限重叠，导致误选更小的数字。