奶牛慢跑

题目链接

奶牛们又出去锻炼蹄子去了！

有 N 头奶牛在无限长的单行道上慢跑，且跑步方向为坐标值增大的方向。

每头奶牛在跑道上开始奔跑的位置互不相同，一些奶牛的奔跑速度可能相同，也可能不同。

由于跑道是单行道，十分狭窄，奶牛们无法相互超越。

当一头速度很快的牛追上另一头牛时，她必须减速至与另一头牛速度相同以免发生碰撞，并成为同一跑步小组的一员。此时，两头牛可以视为在同一点上。

最终，再也没有奶牛会撞到（追上）其他奶牛了。

约翰想知道在这种情况下，会剩下多少个跑步小组。

输入格式

第一行包含整数 N.

接下来 N 行，每行包含一头奶牛的初始位置和跑步速度。

所有奶牛的初始位置各不相同，且是按照递增顺序给出的。

输出格式

输出一个整数，表示最终剩下的小组数量。

数据范围

1≤N≤$10^5$ 初始位置范围 [0,$10^9$]， 跑步速度范围 [1,$10^9$]

输入样例:

5
0 1
1 2
2 3
3 2
6 1

输出样例：

2

思路

本题等价于求连续段数，即每个队的队长数。

如何判断是否为队长？

集合中是否存在一个数小于x，等价于集合中的最小值小于x。

一头牛不会追尾的条件是当前牛的速度大于等于后面所有牛速度的最小值。

从后往前遍历，当遍历到的牛的速度小于最小值速度，证明该头牛为队长，结果加1。

解法一：

#include<iostream>
#include<cstring>
#include<algorithm>


using namespace std;

const int N = 100010,INF = 2e9;


int n;
int v[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        scanf("%*d%d", &v[i]); // 忽略输入
    }
    
    int res = 0, vmin = INF;
    
    for(int i = n - 1; i >= 0; i--) {
        if (v[i] <= vmin) { // 小于最小值，证明该头牛为队长
            res++;
            vmin = v[i];
        }
    }
    printf("%d\n", res);
    return 0;
    
}