题解 | 小猫排队

#include<iostream>
#include<algorithm>
using namespace std;
const int N=200020;
int n,hh=0,tt=-1;
long long w,dq[N];
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&dq[i]);
        tt++;
    }
    scanf("%lld",&w);
    dq[n]=w;
    tt++;
    long long time=0;
    bool can=true;//记录是否可以交换
    while(hh<=tt)
    {
        int idx=tt;
        while(hh<tt&&dq[idx]>=dq[tt]&&can)tt--;
        if(dq[idx]<dq[tt])swap(dq[idx],dq[tt]);//只有当前面存在比w小的数才交换
        else//不能交换，tt不变，can为false
        {
            tt=idx;
            can=!can;
        }
        if(can)
        {
            time++;
            hh++;
        }
        else//不能交换，就没有必要继续判断了
        {
            time+=tt-hh+1;
            break;
        }
    }
    cout<<time;
    return 0;
}