2018CCPC-Wannafly Winter Camp Day7 E. 线性探查法（离散化建图+拓扑排序）

先呈上原题链接

题意：
在大学里选修过数据结构的同学大部分都知道 $hash$hash 算法的线性探查法：

假设有一个元素互不相同的正整数数组 $a[1\dots n]$a[1…n]，我们用以下方法得到数组 $b[1\dots n]$b[1…n]：

初始时 $b\left[i\right]$b[i] 都为 $-1$−1，我们对 $i=1\dots n$i=1…n 依次插入 $a\left[i\right]$a[i] ，假设现在要插入的数是 $x$x ，首先我们找到 $x\%n$x%n 这个位置，如果 $b\left[x\%n\right]=-1$b[x%n]=−1，则令 $b\left[x\%n\right]=x$b[x%n]=x，之后结束这次插入；否则看 $b\left[\right(x+1\left)\%n\right]$b[(x+1)%n] 是否等于 $-1$−1，如果等于则令 $b\left[\right(x+1\left)\%n\right]=x$b[(x+1)%n]=x ，如果不等于，则继续看 $(x+2)\%n\cdots$(x+2)%n⋯，直到找到一个位置。

完成所有插入后，我们会得到一个数组 $b$b，现在给定这个数组 $b$b，你需要求一个字典序最小的 $a[1\dots n]$a[1…n]

思路：

• 首先我们知道，如果某个数 $x$x hash后应该在位置 $pos$pos ,但 $x$x 的实际位置却是在数组 $b$b 的 $i$i 位置，那么 $pos\&gt;i$pos>i 时， $i$i 到 $（pos-1）$（pos−1） 里面这些数都是在 $x$x 插入之前插入的； $pos\&lt;i$pos<i 时， $0$0 到 $（pos-1）$（pos−1） 和 $i$i 到 $（n-1）$（n−1） 里面这些数都是在 $x$x 插入之前插入的。
• 当我们知道某个数 $y$y 一定是在 $x$x 之前插入的，我们就可以从 $y$y 到 $x$x 连一条有向边。然后该图得到的拓扑序列通过线性探测法一定能得到数组 $b$b 。
• 最后一步就是如何得到字典序最小。只需要在拓扑排序的时候用一个优先队列，让所有入度为零的节点的最小的那个值排最前面就行了。

坑点：

无

good luck and have fun!!!

附上代码：

#include<bits/stdc++.h>
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define test(flag,value) cout<<flag<<":"<<(value)<<endl
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int MAXN=1e3+10;
const int MOD=998244353;
const double PI=acos(-1);
int n;
map<int,int> M;
vector<int> G[MAXN];
int in[MAXN];
int b[MAXN];
int ans[MAXN];

void topo()
{
	priority_queue<int,vector<int>,greater<int> >Q;
	for(int i=0;i<n;i++)
		if(in[i]==0)
			Q.push(b[i]);
	int cnt=0;
	while(!Q.empty())
	{
		int val=Q.top();Q.pop();//取优先队列里值最小的
		ans[cnt++]=val;
		int node=M[val];
		int sz=G[node].size();
		for(int i=0;i<sz;i++)
		{
			int x=G[node][i];
			in[x]--;
			if(in[x]==0)
				Q.push(b[x]);
		}
	}
}

int main(void)
{
	scanf("%d",&n);
	mem(in,0);
	for(int i=0;i<n;i++)
	{
		scanf("%d",b+i);
		M[b[i]]=i;//离散化
	}
	for(int i=0;i<n;i++)
	{
		int tmp=b[i];
		int pos=tmp%n;
		if(pos<i)
		{
			for(int j=pos;j<i;j++)
			{
				G[j].pb(i);
				in[i]++;
			}
		}
		else if(pos>i)
		{
			for(int j=0;j<i;j++)
			{
				G[j].pb(i);
				in[i]++;
			}
			for(int j=pos;j<n;j++)
			{
				G[j].pb(i);
				in[i]++;
			}
		}
	}
	topo();
	for(int i=0;i<n;i++)
	{
		if(i==0)
			printf("%d", ans[i]);
		else
			printf(" %d", ans[i]);
	}

}