单调栈做法

算法思想：

• 如果前一个头牛比后一头快，那么必然会与后一头同化
• 单调栈维护一个上升的序列，每次枚举到一头新的牛就把栈中比它速度快的全部弹出，每头牛最多被弹出1次
• 最终栈中的元素数量就是答案

时间复杂度：$O(n)$

在线做法

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int q[N];

int main()
{
    cin>>n;
    int hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        int a,b; cin>>a>>b;
        while(hh<=tt&&q[tt]>b) tt--;
        q[++tt]=b;
    }

    cout<<tt+1<<endl;

    return 0;
}

离线做法

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

using namespace std;

const int N = 100010;

int n;
int q[N], g[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int a,b; cin>>a>>b;
        g[i]=b;
    }

    int hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        while(hh<=tt&&q[tt]>g[i]) tt--;
        q[++tt]=g[i];
    }

    cout<<tt+1<<endl;

    return 0;
}