奶牛慢跑
题目 奶牛慢跑
思路分析
因为跑道是无限长的 且所有奶牛的方向相同
以x轴想象吧 右为正方向
所以从起始位置看 在左边（后面）的速度更快的一定会追上在右边（前面）的速度更小的
对于这个案例来说
3位置（速度2）一定会追到6位置 且速度也变成1
2位置会追到速度变成1的3位置 且自己速度也变成1
1位置会追到速度变成1的2位置 自己也变速度1
只有0号位置（速度1）与他们保持相对静止
所以最终只剩下两个牛队
所以可以从右边（初始位置靠前）开始看
不断维护一个最小的速度 若左边存在某个速度大于这个最小速度 就一定会合并成一个队伍
若左边存在某个速度小于等于这个最小速度 就会是新的队伍 并把这个最小值更新过去
代码实现
#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;
}
💬 评论