题目链接:线性探查法
考虑每个值,如果不在本来的位置上,那么一定是之前的位置被填充了,然后我们可以根据当前的位置,和本来的位置推出一个在他之前被填充的区间。
然后做一个最小字典序拓扑排序即可。不过对于区间连边是 O(n*n)的,需要线段树优化建图。
AC代码:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=4e5+10;
int n,b[N],id[N],cnt,deg[N];
vector<int> g[N];
#define mid (l+r>>1)
void build(int p,int l,int r){
if(l==r){id[p]=l; return ;}
id[p]=cnt++;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
g[id[p<<1]].push_back(id[p]),g[id[p<<1|1]].push_back(id[p]);
deg[id[p]]+=2;
}
void link(int p,int l,int r,int ql,int qr,int v){
if(ql>qr) return ;
if(l==ql&&r==qr){g[id[p]].push_back(v); deg[v]++; return ;}
if(qr<=mid) link(p<<1,l,mid,ql,qr,v);
else if(ql>mid) link(p<<1|1,mid+1,r,ql,qr,v);
else link(p<<1,l,mid,ql,mid,v),link(p<<1|1,mid+1,r,mid+1,qr,v);
}
priority_queue<pair<int,int>> q;
signed main(){
cin>>n; cnt=n; build(1,0,n-1);
for(int i=0,pos;i<n;i++){
cin>>b[i]; pos=b[i]%n;
if(pos==i) q.push({-b[i],i});
else if(pos<i) link(1,0,n-1,pos,i-1,i);
else link(1,0,n-1,pos,n-1,i),link(1,0,n-1,0,i-1,i);
}
while(q.size()){
int u=q.top().second; q.pop();
if(u<n) printf("%d ",b[u]);
for(int to:g[u]) if(--deg[to]==0){
if(to>=n) q.push({0,to});
else q.push({-b[to],to});
}
}
return 0;
}
最后
以上就是清新秋天最近收集整理的关于线性探查法的全部内容,更多相关线性探查法内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复