很明显我们发现若后面的牛比前面的牛速度快,则一定会追上去,并合成一组
所以若想自己成为一组(可能会被后面的牛装上并成为一组)前提要比前面所有的牛速度都要小(可以等于)
所以我们只需要枚举每个位置的后缀最小值即可
注意在这里的位置没有太大的价值,而且是递增的,没有离散化的必要,简化运算这里直接用m++代替
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,res;
int a[N],mi[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
a[++m]=y;
}
mi[m+1]=0x3f3f3f3f;
for(int i=m;i>=1;i--)
{
mi[i]=min(mi[i+1],a[i]);
}
for(int i=1;i<=m;i++)
{
if(a[i]<=mi[i+1])res++;
}
cout<<res;
}