Brute Force Sorting HDU - 6215

本文主要是介绍Brute Force Sorting HDU - 6215，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=6215

一开始直接拿链表来模拟 但是这样每删一遍数组都要从链表表头开始 有太多无谓的操作 后来看了学长博客才想到

解决这样的问题可以想到用一个类似队列或栈的数组优化 提前把所有可能要操作的位置存下来 复杂度就接近线性了

数组中保存的就是可能从该点开始产生非排序序列的下标 每次都删掉一段 下次再来到被删掉的位置直接跳过

#include <bits/stdc++.h>
using namespace std;
const int N=0x3f3f3f3f;int ary[100010],pre[100010],nxt[100010],tmp[100010];
int n,len,cnt,ans;int main()
{int t,i,flag,cur,p,num;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&ary[i]);ary[0]=-1,ary[n+1]=N;for(i=0;i<=n+1;i++){pre[i]=i-1;nxt[i]=i+1;tmp[i]=i;}len=n,ans=n;while(1){cnt=0,flag=1,cur=1;while(cur<=len){p=tmp[cur],num=0;while(nxt[p]<=n&&ary[p]>ary[nxt[p]]){num++;p=nxt[p];flag=0;}if(num!=0){ans-=(num+1);nxt[pre[tmp[cur]]]=nxt[p];pre[nxt[p]]=pre[tmp[cur]];tmp[++cnt]=pre[tmp[cur]];}while(tmp[cur]<=p&&cur<=len) cur++;}len=cnt;if(flag==1) break;}printf("%d\n",ans);cur=nxt[0],cnt=1;while(cur<=n){printf("%d ",ary[cur]);cur=nxt[cur],cnt++;}printf("\n");}return 0;
}

 

这篇关于Brute Force Sorting HDU - 6215的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---