题意
给你一个队列和集合,和中各有个元素,这个元素为个以及被随机分配到队列和集合中。每次可以从队列出队一个数字然后将其加入集合中,再从集合中取出一个数入队,问将队列中的元素从队首到队尾变为需要的最小操作次数。
题解
首先操作的上界是次,将队列中都变为,然后按从大到小的顺序入队即可。那么此外首先考虑特殊情况,当队列中一开始的情况是,集合中的元素为和时,这样只需要再次操作即可实现。那么别的情况下怎么操作呢,例如,为时,的初始位置在,但其的目标位置在,所以他必须先完成两次出队之后,再经过两次入队才能到达目标位置。同理的初始位置在,目标位置在,它需要出队次再入队次才可以达到目标。所以对于数字来说它的必须次数为。因为要所有数字都满足所以要取个最大值。遍历一遍所有数即可。
复杂度
时间复杂度
代码
#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; }