小猫排队
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
世界上最苦恼的事情莫过于排队了，特别是排在你前面的猫比你可爱的时候。----《论猫的自我修养》
小猫啾啾现在就很苦恼，它排在队伍的末尾处等着买酱油，前面还有足足n nn只猫咪。但幸运的是小猫啾啾会一种魔法：它可以和前面距离它最近且比它可爱（可爱值大于啾啾）的小猫交换位置（被交换的小猫会被传送到啾啾之前的位置）。
已知啾啾每一分钟开始时可以施展一次魔法，而每一分钟过后排在队伍最前面的猫咪就会离开队伍（这意味这啾啾会先交换位置然后队伍才开始移动）。
因为等会还得去买饺子所以啾啾会尽可能地与自身前方比它可爱且未出队的小猫交换位置（可以证明交换后必定更快买到酱油），现在啾啾想请你帮它计算出它需要多久才能买到酱油离开。
输入描述：
第一行一个整数n nn代表啾啾前方小猫的数量。
第二行n nn个用空格隔开的整数代表从队伍最前方到队尾每只小猫的可爱值。
第三行一个整数代表啾啾的可爱值。
1 ≤ n ≤ 2 ⋅ 1 0 5 1≤n≤2⋅10^51≤n≤2⋅105
1 ≤ 可爱值 ≤ 1 0 9 1≤可爱值≤10^91≤可爱值≤109
输出描述：
一行一个整数代表啾啾需要几分钟才能买到酱油离开队伍。
示例1
输入：
6 9 7 3 7 6 2 5输出：
4说明：
用∗ *∗表示啾啾的位置：
- 起始时：973762 ∗ 9 7 3 7 6 2 *973762∗（无人出队）
- 第一分钟时：737 ∗ 26 7 3 7 * 2 6737∗26（9 99已出队）
- 第二分钟时：3 ∗ 726 3 * 7 2 63∗726（9 997 77已出队）
- 第三分钟时：∗ 726 * 7 2 6∗726（9 997 773 33已出队）
- 第四分钟时：7 772 226 66（9 997 773 33∗ *∗已出队）
示例2
输入：
1 5 2输出：
1说明：
第一分钟开始的时候啾啾就已经到了队首，所以在第一分钟结束时啾啾就会出队。
解题思路
首先读取前方小猫数量n nn、可爱值数组a aa和啾啾的可爱值x xx，遍历数组将所有可爱值大于x xx的小猫的索引压入栈中（记录可交换的目标位置，栈中按遍历顺序存储索引）；随后初始化左指针l = 0 l=0l=0、右指针r = n r=nr=n和答案a n s = 0 ans=0ans=0，进入循环处理：若栈非空且栈顶索引≥ l ≥l≥l（说明当前存在可交换的小猫），则将r rr更新为该栈顶索引并弹出栈顶（调整啾啾的目标位置，实现交换），之后l ll自增、a n s ansans自增（模拟时间流逝和队伍最前方小猫出队）；该过程通过栈高效维护可交换的索引，利用双指针模拟啾啾的交换和出队过程，时间复杂度为O ( n ) O(n)O(n)，适配n nn达2 e 5 2e52e5的规模，无需模拟复杂的交换操作，直接通过索引处理精准计算出啾啾买到酱油所需的时间。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e5+10;ll a[N];intmain(){ll n;cin>>n;for(ll i=0;i<n;i++)cin>>a[i];ll x;cin>>x;stack<ll>stk;for(ll i=0;i<n;i++){if(a[i]>x)stk.push(i);}ll l=0,r=n;ll ans=0;while(l<=r){if(stk.size()&&stk.top()>=l){r=stk.top();stk.pop();}l++,ans++;}cout<<ans<<endl;return0;}
