/ Vijos / 题库 /

你追我赶

你追我赶

时间限制:1秒  内存限制:256M


【问题描述】

  小M和小Y决定来一次跑步比赛,他们从同一起点同时出发,沿着笔直的公路向前奔跑……

  他们的跑步速度在一些时间段内是恒定的。比如:小H在前3个时间段速度是5,接着6个时间段内速度是10。他们的比赛总时间相同。他们希望能统计出在整个比赛过程中领先顺序的变化次数。举个例子,某个时刻小H领先,下个时刻小Y领先,这就是一次领先顺序的变化;如果某个时刻小H领先,接下来一段时间小Y赶上来并和小H齐头并进,但最终还是超过了小H,这也是一次领先顺序的变化,当然,如果没有超过,则不算领先次序的变化;要特别注意的是:最开始,小H和小Y同时同地出发后,第一次出现某人领先的情况不能算领先次序的变化。

【输入格式】

  第1行:\(N\) 和 \(M\)。
  接下来的 \(N\) 行:每行两个整数,描述小H跑步的一段,分别表示该段小H跑步的速度和持续这种速度的时间。所有的数据范围 [1..1000]。
  再接下来的 \(M\) 行:每行两个整数,描述小Y跑步的一段,分别表示该段小Y跑步的速度和持续这种速度的时间。所有的数据范围 [1..1000]。

【输出格式】

  一行:整个比赛过程中领先顺序的变化次数。

【输入输出样例】

 Input

4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9

 Output

2

【输入输出样例解释】

  小H在前2个单位时间内速度是1,接着1个单位时间内速度是4,接着1个单位时间内速度是1,最后10个单位时间内速度是2。小Y在前3个个单位时间内速度是2,接着2个单位时间内速度是1,最后9个单位时间内速度是3。

  比赛开始后小Y领先,直到第5个单位时间小H超过小Y(第一次领先顺序变化),接着第7个单位时间时,小Y又反超小H,变成领先(第二次领先顺序变化)

【数据限制】

  \(100\%\) 的数据满足,\(1 ≤ N, M ≤ 1000\)。

【来源】

   Mr.he

信息

ID
1364
难度
2
分类
模拟 点击显示
标签
递交数
2
已通过
1
通过率
50%
被复制
4
上传者