#PU489. USACO 2014 December Contest, Bronze — Problem 3. Cow Jog
USACO 2014 December Contest, Bronze — Problem 3. Cow Jog
USACO 2014 December Contest, Bronze — Problem 3. Cow Jog
题目描述
Problem 3: Cow Jog [Mark Gordon, 2014]
The cows are out exercising their hooves again! There are N cows
jogging on an infinitely-long single-lane track (1 <= N <= 100,000).
Each cow starts at a distinct position on the track, and some cows jog
at different speeds.
With only one lane in the track, cows cannot pass each other. When a
faster cow catches up to another cow, she has to slow down to avoid
running into the other cow, becoming part of the same running group.
Eventually, no more cows will run into each other. Farmer John
wonders how many groups will be left when this happens. Please help
him compute this number.
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5
0 1
1 2
2 3
3 2
6 1
2