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

题目链接:线性探查法


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

然后做一个最小字典序拓扑排序即可。不过对于区间连边是 O(n*n)的,需要线段树优化建图。


AC代码:

复制代码
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; }

最后

以上就是清新秋天最近收集整理的关于线性探查法的全部内容,更多相关线性探查法内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(80)

评论列表共有 0 条评论

立即
投稿
返回
顶部