---
title: "奶牛慢跑"
created: 2025-11-28
tags:
  - 算法
---

# 奶牛慢跑

## 题目  [奶牛慢跑](https://www.acwing.com/problem/content/description/1906/)

![[image-84edc9b8.png]]

## 思路分析

因为跑道是无限长的 且所有奶牛的方向相同

以x轴想象吧 右为正方向

所以从起始位置看 在左边（后面）的速度更快的一定会追上在右边（前面）的速度更小的

![[image-0d6611ce.png]]

对于这个案例来说

3位置（速度2）一定会追到6位置 且速度也变成1

2位置会追到速度变成1的3位置 且自己速度也变成1

1位置会追到速度变成1的2位置 自己也变速度1

只有0号位置（速度1）与他们保持相对静止

所以最终只剩下两个牛队

所以可以从右边（初始位置靠前）开始看

不断维护一个最小的速度 若左边存在某个速度大于这个最小速度 就一定会合并成一个队伍

若左边存在某个速度小于等于这个最小速度 就会是新的队伍 并把这个最小值更新过去

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10,INF=2e9;

int st[N];

int top=-1;

int n;

int main()

{

    cin>>n;

    while(n--){

        int idx,v;

        cin>>idx>>v;

        st[++top]=v;

    }

    int res=0,vmin=INF;

    while(top!=-1){

        if(st[top]<=vmin){

            res++;

            vmin=st[top];

        }

        top--;

    }

    cout<<res<<endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[包装机|包装机]] 🏠 [[00-刷题理模型]] ➡️ [[字符串|字符串]]