题目链接:CCPC-Wannafly 2018WC Day7 E.线性探测法
题意:
给一个长度为n的数组b[i],表示经过hash之后的数组,求原数组的最小字典序。
题解:
如果b[i]%n=i,表示刚好在原位,即没有产生冲突。所以当b[i]%n!=i时,则区间[b[i]%n,i-1]中所有的数都在b[i]之前,由该区间向该点建边,然后拓扑排序即可。
小数据可以暴力建图,大数据需要线段树优化建图。
参考代码:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+9;
const int MAXM=1e3+9;
const int inf=1e3+9;
int n;
int deg[MAXN<<3],pos[MAXN<<3],id[MAXN<<3],b[MAXN];
struct Edge
{
int v,nxt;
} edge[MAXN<<3];
int fir[MAXN<<3],cnt=0;
void addedge(int u,int v)
{
edge[cnt].v=v;
edge[cnt].nxt=fir[u];
fir[u]=cnt++;
deg[v]++;
}
void build(int l,int r,int rt)
{
id[rt]=-1;
if(l==r)
{
pos[l]=rt;
id[rt]=l;
return;
}
addedge(rt<<1,rt);
addedge(rt<<1|1,rt);
int mid=(l+r)/2;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
}
void ADDEDGE(int L,int R,int p,int l,int r,int rt,bool flag)
{
if(L<=l&&r<=R)
{
if(flag)
addedge(rt,p);
else
addedge(p,rt);
return;
}
int mid=(l+r)/2;
if(L<=mid)
ADDEDGE(L,R,p,l,mid,rt<<1,flag);
if(R>mid)
ADDEDGE(L,R,p,mid+1,r,rt<<1|1,flag);
}
void topo()
{
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;
while(!que.empty())
que.pop();
for(int i=0; i<n; i++)
if(!deg[pos[i]])
que.push({b[i],pos[i]});
vector<int> ans;
ans.clear();
while(!que.empty())
{
pair<int,int> p=que.top();
que.pop();
int u=p.second;
if(p.first!=-1)
ans.push_back(p.first);
for(int i=fir[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
if(--deg[v]==0)
{
if(id[v]==-1)
que.push({-1,v});
else
que.push({b[id[v]],v});
}
}
}
for(int i=0; i<ans.size(); i++)
if(i==0)
printf("%d",ans[i]);
else
printf(" %d",ans[i]);
}
int main()
{
scanf("%d",&n);
memset(fir,-1,sizeof(fir));
memset(deg,0,sizeof(deg));
for(int i=0; i<n; i++)
scanf("%d",&b[i]);
build(0,n-1,1);
for(int i=0; i<n; i++)
{
int s=b[i]%n,t=i;
if(s==t)
continue;
if(s<t)
ADDEDGE(s,t-1,pos[i],0,n-1,1,1);
else
{
if(t)
ADDEDGE(0,t-1,pos[i],0,n-1,1,1);
ADDEDGE(s,n-1,pos[i],0,n-1,1,1);
}
}
topo();
return 0;
}