【题解】队列和集合

题意

给你一个队列和集合，和中各有个元素，这个元素为个以及被随机分配到队列和集合中。每次可以从队列出队一个数字然后将其加入集合中，再从集合中取出一个数入队，问将队列中的元素从队首到队尾变为需要的最小操作次数。

题解

首先操作的上界是次，将队列中都变为，然后按从大到小的顺序入队即可。那么此外首先考虑特殊情况，当队列中一开始的情况是，集合中的元素为和时，这样只需要再次操作即可实现。那么别的情况下怎么操作呢，例如，为时，的初始位置在，但其的目标位置在，所以他必须先完成两次出队之后，再经过两次入队才能到达目标位置。同理的初始位置在，目标位置在，它需要出队次再入队次才可以达到目标。所以对于数字来说它的必须次数为。因为要所有数字都满足所以要取个最大值。遍历一遍所有数即可。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int vis[N],s[N],q[N];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1; i<=n; i++)
    {
        scanf("%d",&q[i]);
        vis[q[i]]=i;
    }
    for (int i=1; i<=n; i++)
        scanf("%d",&s[i]);
    if (vis[n])
    {
        for(int i=n,j=1;vis[i]==vis[n]+j-1;j++,i--)
        {
            if(vis[i]==n)
            {
                int k=i-1;
                while(k>=1&&vis[k]==0) k--;
                if(k==0)
                {
                    printf("%d\n",i-1);
                    return 0;
                }
            }
        }
    }
    int ans=0;
    for (int i=1; i<=n; i++)
        ans=max(ans,vis[i]+i);
    printf("%d\n",ans);
    return 0;
}