线性探查法

121 阅读 0 评论 80 点赞

我是靠谱客的博主清新秋天，这篇文章主要介绍线性探查法，现在分享给大家，希望可以做个参考。

题目链接：线性探查法

考虑每个值，如果不在本来的位置上，那么一定是之前的位置被填充了，然后我们可以根据当前的位置，和本来的位置推出一个在他之前被填充的区间。

然后做一个最小字典序拓扑排序即可。不过对于区间连边是 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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;
}