#P2667. Barber's problem
Barber's problem
题目描述
汤姆是一个小镇的理发师。他拥有一家小商店、几个学徒,并因其高质量的服务而赢得了良好的声誉。然而,随着他的客户越来越多,他遇到了一些问题。
让我们先看一下理发的过程。顾客可以换衣服理发;洗完头发后,开始理发;之后再洗一次头发,擦干头发,把衣服换回去,然后付钱。在 Tom 的商店里,他自己做所有理发、干活和现金工作,把换衣服和洗头的工作留给他的学徒。假设每个作需要 1 个单位的时间,如图 1 所示。
通常,Tom 会对整个过程进行管道化处理,以便他可以同时为多个客户提供服务。以下是两个客户的简单案例:
但是,当三个客户走到一起时,简单的管道将满足问题:
在时间 5 和时间 7 时,客户 1 和 3 都需要 Tom。太可惜了,汤姆只能在 1 个单位的时间内做一件事,但他怎么能让他的客户湿着头发等他呢?
当然,这对汤姆来说没什么大不了的。他只是在他的程序中添加了一些 wait 单元,如图 4 所示:
没有人会抱怨理发和吹干后休息一下,现在所有三位顾客都得到了及时的服务(图 5)。
但是,对于更复杂的情况,汤姆应该怎么做呢?
现在 需要你的帮助。假设 能够知道客户何时到来,您将判断是否可以在程序中添加一些等待单位以满足:
- 让所有顾客一来就得到服务(顾客不耐烦,不能及时服务就走)。
- 消除管道中的碰撞(碰撞意味着 Tom 必须同时服务两个以上的客户,但可以同时服务许多客户换衣服或洗头,因为学徒足够)。
您需要记住的其他一些注意事项:
- 您添加的等待单位必须是有限的。
- 等待单元可以是相邻的。
- 每个客户的程序都应该相同。没有人比其他人乐意等待更长的时间。
- 您只能将等待单位添加到程序中,而不能交换或删除任何现有步骤。必须保留原始顺序:Change-Wash-Cut-Wash-Dry-Change-Pay。
输入
输入中有多个测试用例。
以下几行描述了测试用例。一个 的每一行都以以下格式给出:
它给出了客户来的时间。 表示每个 的间隔时间。括号表示客户会定期来。
例如,假设第一个客户在时间 1 到达,如果客户到达时间 1、3、5、7、9、11、13、... 表示形式为 (2)
。表示 (1,3,7)
表示客户将在时间 1、2、5、12、13、16、23、24、27、34...
图 5 所示的示例对应于表示 (1)
,当然,在 4、5、6、7 等时间会有更多的客户来......
包含 (0)
的行结束输入。
输出
您的任务是决定是否有解决方案将 FINITE 等待单位添加到理发程序中,以消除管道中的冲突,并使所有客户都能在他来后立即得到服务。如果可以解决,则打印 Yes
,否则打印 No
,分别在一行中。
例如,对于输入 (1)
,您可以添加 2 个等待单位,如上图 5 所示,以解决 个客户的情况,但是当越来越多的客户来时,除了添加越来越多的等待单位外,您无法满足所有人。没有尽头。所以答案是 No
。对于输入 (2,3,7)
,您可以在过程中添加 4 个等待单位 以满足管道,如图 6 所示。所以答案是 Yes
。
输入数据 1
(1)
(2,3,7)
(0)
输出数据 1
No
Yes
来源
北京 2005 预选赛