题意:给你长度为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("");
}
}

最新文章

  1. 如何查看mysql数据库的端口
  2. [.NET逆向] .net IL 指令速查(net破解必备)
  3. Ajax跨域访问XML数据的另一种方式——使用YQL查询语句
  4. 泛型中? super T和? extends T的区别
  5. C# 事务处理
  6. hdu 3062
  7. Topcoder SRM 648 (div.2)
  8. 监控工具zabbix
  9. 数据库操作CURD
  10. VC 绘图技巧--自定义形状图形
  11. 关于args的一个小bug
  12. nodejs+websocket实时聊天系统
  13. 关于word2016中mathtype无法使用以及“由于宏安全设置,无法找到宏或宏已被禁用”的解决方案
  14. SoftMax regression
  15. 学习ASP.NET Core Razor 编程系列十一——把新字段更新到数据库
  16. vue内置指令与自定义指令
  17. ARM 汇编指令 DCD
  18. 【Python入门只需20分钟】从安装到数据抓取、存储原来这么简单
  19. js知识点: 数组
  20. POJ 1068&amp;&amp;2632&amp;&amp;1573&amp;&amp;2993&amp;&amp;2996

热门文章

  1. jformdesigner 开发
  2. Jquery如何禁止鼠标右键菜单
  3. Vue--项目开发之实现tabbar功能来学习单文件组件1
  4. zhuan 常用图像数据集:标注、检索
  5. ubuntu默认启动方式修改 psensor命令
  6. Zookeeper的实际应用
  7. 1.3 CPU简介
  8. easyui datagrid 首次不加载做法
  9. Linux文件系统命令 lsof
  10. netty---------write flush两个方法到底做了什么?