题意:给你长度为n的数组,定义已经排列过的串为:相邻两项a[i],a[i+1],满足a[i]<=a[i+1]。我们每次对当前数组删除非排序过的串,合并剩下的串,继续删,直到排序完成。
题解:用双向链表模拟删除过程即可。
具体细节见代码:
#include<cstdio>
#include<cstring>
#define N 200010
using namespace std;
int T,n,i,a[N],out[N],next[N],pre[N],r,pos[N],l;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
l=r=;
memset(pos,,sizeof(pos));
memset(out,,sizeof(out));
memset(next,,sizeof(next));
memset(pre,,sizeof(pre));
for(i=;i<=n;i++){
scanf("%d",&a[i]);
next[i]=i+;
pre[i]=i-;
if(a[i]<a[i-]){///标记第一次遍历所删除的数
if(!out[i-])pos[++r]=i-,out[i-]=;///r表示所删除的数的数量
pos[++r]=i;out[i]=;
}
}
for(l=;l<=r;){
int rr=r;
for(i=l;i<=rr;i++){
next[pre[pos[i]]]=next[pos[i]];
pre[next[pos[i]]]=pre[pos[i]];///将pos[i]所表示的数删去
if(pre[pos[i]]==||next[pos[i]]==n+)continue;///遍历完毕
if(!out[next[pos[i]]]&&a[next[pos[i]]]<a[pre[pos[i]]]){///如果已经删除的数后面一个数并未被删除,且这一个数小于已经删除的数的前一个数,那么则删除它
if(!out[pre[pos[i]]])pos[++r]=pre[pos[i]],out[pre[pos[i]]]=;
pos[++r]=next[pos[i]];out[next[pos[i]]]=;
}
}
l=rr+;
}
printf("%d\n",n-r);
for(i=;i<=n;i++)
if(!out[i])printf("%d ",a[i]);puts("");
}
}