37分的人一定WA on #4,相信你是这么做的:
按时间推进工序安排,每次更新时间后更新机器状态并从头到尾检索待办列表,可以进行下一步的工件放到机器里加工。
这样你会在#4得出一个比标准答案快三个单位时间的答案。效率很高但是错了,为什么呢?
题目原文如下:
还要注意,“安排顺序”只要求按照给定的顺序安排每个操作。
当一个操作插入到某台机器的某个空档时(机器上最后的尚未安排操作的部分也可以看作一个空档),可以靠前插入,也可以靠后或居中插入。为了使问题简单一些,我们约定:在保证约束条件 (1.)(2.) 的条件下,尽量靠前插入。并且,我们还约定,如果有多个空档可以插入,就在保证约束条件 (1.)(2.) 的条件下,插入到最前面的一个空档。于是,在这些约定下,上例中的方案一是正确的,而方案二是不正确的。
可以发现一个事情,原文强调一个概念叫做靠前插入,37分的同学们听好了,你们肯定只关注了靠前两个字,完全不在意后面的插入指的是什么(不要问我为什么这么深刻因为我就是踩坑的人之一 )。
事实上,插入二字在原文中一直很重要,它提示了一个关键的信息,即我们要做的事情是对着一个代办列表从前到后安排每个操作,这意味着我们需要做的是对照时间表将操作填入空缺或者追加到末尾,而不是在每个时间点扫描代办列表并将工件放到机器里,这二者会带来根本差别。
总结一下,37分的同学们审错题目啦!所以如果你是在写了一两个小时之后对着完美的样例输出和37pts一脸懵逼的人,现在回去只需要干一件事:
删干净,重新写