1904. 奶牛慢跑
摘要
Title: 1904. 奶牛慢跑
Tag: 思维
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1904. 奶牛慢跑
-
题意
奶牛们又出去锻炼蹄子去了！
有 N 头奶牛在无限长的单行道上慢跑，且跑步方向为坐标值增大的方向。
每头奶牛在跑道上开始奔跑的位置互不相同，一些奶牛的奔跑速度可能相同，也可能不同。
由于跑道是单行道，十分狭窄，奶牛们无法相互超越。
当一头速度很快的牛追上另一头牛时，她必须减速至与另一头牛速度相同以免发生碰撞，并成为同一跑步小组的一员。此时，两头牛可以视为在同一点上。
最终，再也没有奶牛会撞到（追上）其他奶牛了。
约翰想知道在这种情况下，会剩下多少个跑步小组。 -
思路
最终追尾成一个点的牛，必然是一个连续的段
求区间数 = 求每个区间的队长数（最右边的牛） = 判断每个牛是不是队长 = 判断这个牛会不会不追尾右边的牛 = 判断这个牛的速度是不是小于等于右边所有牛速度的最小值 -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28'''
Author: NEFU AB-IN
Date: 2022-01-22 19:50:29
FilePath: \ACM\Acwing\1904.py
LastEditTime: 2022-01-22 21:02:32
'''
'''
最终追尾成一个点的牛，必然是一个连续的段
求区间数 = 求每个区间的队长数（最右边的牛） = 判断每个牛是不是队长 = 判断这个牛会不会$不追尾$右边的牛 = 判断这个牛的速度是不是小于等于右边所有牛速度的最小值
'''
lst = []
INF = int(2e9)
if __name__ == "__main__":
n = int(input())
for _ in range(n):
x, v = map(int, input().split())
lst.append(v)
vmin = INF
res = 0
for i in range(n - 1, -1, -1):
if lst[i] <= vmin:
res += 1
vmin = lst[i]
print(res)