题目描述(ID:12371)
标题: 大堵车
标签: 贪心 模拟
详情:
编程星球上有一些繁忙的道路常年堵车。在一条单行道上,有N辆车正在不同的位置d上以不同速度v行驶。由于道路是单行道,后面的车辆无法超过前面的车辆,因此当一辆快车跟在慢车后面时,它必须把速度降低到和慢车一致,以免发生撞车。于是这两辆车就形成了一个共同前进的车队。经过长时间的行驶,所有的车会形成若干个车队。
为了缓解拥堵情况,啊哈沃德需要计算最终形成了多少个车队。请写出程序帮助他。
输入格式:
第一行包含一个正整数N,(1<=N<=100000)。
接下来N行,每行包括两个整数di和vi,表示第i辆车的位置和速度。(0<=di<=1000000000, 0<=vi<=1000000000,di从小到大顺序,越大表示车位置越靠前)
输出格式:
一个正整数,表示最终车队的数量
限制: 对于30%数据,N<=1000
对于50%数据,N<=50000
对于100%数据,N<=100000
样例:

输入

5
3 2
7 4
11 6
15 4
22 2

输出

2

解释

经过一段时间行驶后,位于22的车在最前面,15,11,7的车速度降低到和22一致,形成一个车队。位于3的车单独形成第二个车队,因此一共有2个车队。
登录并解答