#P1017. 伴舞僵尸的进攻
伴舞僵尸的进攻
"僵王博士又来了!这次他带来了他的太空步军团!" —— 疯狂戴夫
题目背景
那是一个风雨交加的夜晚,疯狂戴夫正在前院照料他的豌豆射手。突然,远处的草坪上传来了迪斯科球的闪光和震耳欲聋的音乐声——是僵王博士的太空步僵尸军团!僵王博士站在屋顶上,挥舞着指挥棒,派出了 只伴舞僵尸作为先头部队。
这些伴舞僵尸穿着闪亮的舞衣,踩着迈克尔·杰克逊的太空步,试图用舞蹈征服戴夫的草地。当动感的音乐响起,伴舞僵尸们将按照既定的节奏陆续登场,然后开始召唤更多的舞伴,向四面八方扩散。
戴夫看着他的向日葵们吓得瑟瑟发抖,叹了口气:"我需要知道,这些家伙到底要跳多久才能占满整个院子……"
题面描述
具体规则如下:
- 第 只伴舞僵尸将在第 秒出现于数轴上的坐标 处。
- 每一只位于坐标 的伴舞僵尸,在它出现的一秒后以及此后的每一秒,都会在其相邻的两个整数坐标 和 处各召唤一只新的伴舞僵尸。被新召唤的伴舞僵尸同样拥有上述召唤能力,且同一个坐标处可以同时存在多只伴舞僵尸。
僵王博士的目标是用伴舞僵尸覆盖整个战场。问:至少需要多少秒,才能保证数轴上区间 内的每个整数坐标都至少存在一只伴舞僵尸?
Input
第一行包含两个整数 (, ),分别表示伴舞僵尸的总数和需要覆盖区间的右端点。
接下来 行,每行包含两个整数 (),分别表示第 只伴舞僵尸的出现时间和初始位置。
Output
输出一行一个整数,表示伴舞僵尸覆盖数轴上 区间内所有整数坐标所需的最短时间。
3 5
0 0
0 5
1 2
2
2 102
0 102
6 66
72
Notes
对于第一个样例,在每一秒结束时,数轴上 区间内各坐标的伴舞僵尸数量如下:
- 第 秒:;
- 第 秒:;
- 第 秒:。
在第 秒时,数轴上 区间内的每个整数坐标处都至少存在一只伴舞僵尸。