USACO2014DEC 铜组第三题

题目描述

奶牛们又出来锻炼蹄子啦！有 ( N ) 头奶牛（( 1 <= N <= 100,000 ) ）在一条无限长的单车道跑道上慢跑。每头奶牛初始位置不同，且部分奶牛速度不同。

由于只有一条车道，奶牛无法超车。当速度快的奶牛追上前面的奶牛时，必须减速，避免撞到前面的牛，最终和前面的牛组成同一跑步小组。

最终，不会再有奶牛相互追上。农夫约翰想知道，最后会剩下多少个跑步小组。请帮他计算这个数量。

输入格式

• 第 1 行：整数 ( N )（奶牛数量 ）。
• 第 2 至 ( N+1 ) 行：每行包含两个整数，分别表示奶牛的初始位置（非负整数，最大 10 亿 ）和速度（正整数 ）。输入的奶牛按初始位置递增顺序给出（位置互不相同 ）。

样例输入

5
0 1
1 2
2 3
3 2
6 1

输入详情
5 头奶牛，初始位置依次为 0、1、2、3、6，速度分别为 1、2、3、2、1 。

输出格式

输出 1 行，为最终剩下的跑步小组数量。

样例输出

2

输出详情

• 第 5 头奶牛（位置 6，速度 1 ）无法追上前面的牛，自成一组。
• 前 4 头奶牛中，速度最快的是第 3 头（速度 3 ），但会被后面的牛追上合并：
  • 第 3 头（速度 3 ）会追上第 4 头（速度 2 ），合并后速度变为 2；
  • 合并后的小组继续追上更前面的牛，最终前 4 头奶牛合并为一组；
• 总共有 2 个小组（前 4 头一组，第 5 头一组 ）。