#5438. Problem 3. Cow Jog
0
Problem 3. Cow Jog
好的,这是您提供的 USACO 2014 年 12 月竞赛 Gold 组第三题 Cow Jog 的中文翻译:
问题 3. 牛的慢跑 (Cow Jog)
USACO 2014 年 12 月竞赛,Gold 组
农夫约翰的 头奶牛()正在跑道上锻炼蹄子。每头牛都从跑道上一个不同的初始位置开始,并且有些奶牛以不同的速度奔跑。
跑道被分成若干车道,以便奶牛可以相互超越。同一车道内的奶牛任何时刻都不能占据相同的位置。农夫约翰不希望任何奶牛需要改变车道或调整速度,因此他想知道,如果奶牛们要奔跑 分钟(),他至少需要多少条车道才能满足要求。
输入 (文件 cowjog.in):
第一行包含 和 。
接下来的 行,每行包含一头奶牛的初始位置和速度。位置是非负整数,速度是正整数;这两个数字都不超过 10 亿。所有奶牛的初始位置都不同,并且输入中的位置是按递增顺序给出的。
输出 (文件 cowjog.out):
一个单独的整数,表示完成此任务所需的最小车道数,使得同一车道内的任意两头牛在任何时刻(包括时间 时)都不会占据相同的位置。
示例输入:
5 3 0 1 1 2 2 3 3 2 6 1
示例输出:
3