小猫排队（牛客）

小猫排队（牛客）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

世界上最苦恼的事情莫过于排队了，特别是排在你前面的猫比你可爱的时候。----《论猫的自我修养》

小猫啾啾现在就很苦恼，它排在队伍的末尾处等着买酱油，前面还有足足 转存失败重新上传取消 只猫咪。但幸运的是小猫啾啾会一种魔法：它可以和前面距离它最近且比它可爱（可爱值大于啾啾）的小猫交换位置（被交换的小猫会被传送到啾啾之前的位置）。

已知啾啾每一分钟开始时可以施展一次魔法，而每一分钟过后排在队伍最前面的猫咪就会离开队伍（这意味这啾啾会先交换位置然后队伍才开始移动）。

因为等会还得去买饺子所以啾啾会尽可能地与自身前方比它可爱且未出队的小猫交换位置（可以证明交换后必定更快买到酱油），现在啾啾想请你帮它计算出它需要多久才能买到酱油离开。

输入描述:

第一行一个整数 转存失败重新上传取消 代表啾啾前方小猫的数量。

第二行 1个用空格隔开的整数代表从队伍最前方到队尾每只小猫的可爱值。

第三行一个整数代表啾啾的可爱值。

输出描述:

一行一个整数代表啾啾需要几分钟才能买到酱油离开队伍。

示例1

输入

复制6 9 7 3 7 6 2 5

6
9 7 3 7 6 2
5

输出

复制4

4

说明

用*表示啾啾的位置：

起始时：9 7 3 7 6 2 *（无人出队）

第一分钟时：7 3 7 * 2 6（9已出队）

第二分钟时：3 * 7 2 6（9 7已出队）

第三分钟时：* 7 2 6（9 7 3已出队）

第四分钟时：7 2 6（9 7 3 *已出队）

示例2

输入

复制1 5 2

1
5
2

输出

复制1

1

说明

第一分钟开始的时候啾啾就已经到了队首，所以在第一分钟结束时啾啾就会出队。

思路：因为只能传输到比小猫可爱值大的小猫的位置，所以我们可以用栈来储存比小猫可爱值大的数的下标，每次传输的时候取栈顶元素再删除，因为每分钟也有队头的小猫出队，所以我们需要用一个数l来记录队头的小猫的下标，当队头的下标小于等于小猫所在位置的下标的时候说明他还没有出队，当他没有出队的时候我们需要判断他要交换的栈顶元素（大于可爱值的下标）是否大于等于l，如果大于等于说明他前面可爱值比他大的小猫还没有出队，可以交换，（注意，等于的情况是队头的小猫可爱值恰好大于指定数值，根据题意是先交换再出队，所以等于情况也满足）交换过后l++，操作步数++，最后输出操作步数即可。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
stack<int> st;
const int N=2e5;
int a[N];
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int p;scanf("%d",&p);for(int i=1;i<=n;i++){if(a[i]>p){st.push(i); }}int l=1,idx=n+1,con=0;//小猫前有n个猫，所以他在n+1的位置do{if (!st.empty() && st.top() >= l){//如果栈不空且可爱值大于我们小猫的下标大于等于队头小猫的下标时idx= st.top();st.pop();}l++, con++;} while (l <= idx);//当队头小猫的下标小于我们的小猫所在的位置（我们小猫还没有出队时printf("%d",con);return 0;
}