题目

Given a hash table of size N, we can define a hash function H(x)=x%N. Suppose that the linear probing is used to solve collisions, we can easily obtain the status of the hash table with a given sequence of input numbers.

However, now you are asked to solve the reversed problem: reconstruct the input sequence from the given status of the hash table. Whenever there are multiple choices, the smallest number is always taken.

Input Specification:
Each input file contains one test case. For each test case, the first line contains a positive integer N (≤1000), which is the size of the hash table. The next line contains N integers, separated by a space. A negative integer represents an empty cell in the hash table. It is guaranteed that all the non-negative integers are distinct in the table.

Output Specification:
For each test case, print a line that contains the input sequence, with the numbers separated by a space. Notice that there must be no extra space at the end of each line.

Sample Input:

11
33 1 13 12 34 38 27 22 32 -1 21

Sample Output:

1 13 12 21 33 34 38 27 22 32

分析

题目大意：从已经确定的散列表中（解决冲突的方法是“线性探测”），找出输入序列

大体思路是把数与数的关系抽象成一张有向图，再用拓扑排序输出

由例子可以看出，比如 1%11 = 1，12%11 = 1，但是 12 排在 1 的后面存储，说明肯定 1 比 12 先输入，而根据线性探测，12 就该存在第二个位置，而现在第二个位置是 13，说明 13 也肯定比 12 先输入，即只有 1 和 13 输入后 12 才能输入，…， 由此可以建立一张有向图，只有前面的结点输入后，后面的结点才能被输入

再进行拓扑排序，要求按从小到大输出，所以用到了STL的最小堆，但是最小堆存的只是值，还要根据值找回下标，又用到了STL的map

#include<queue>
#include<iostream>
#include<vector>
#include<map>
#define INF -100000
#define MaxVertex 1005
int G[MaxVertex][MaxVertex];
int Indegree[MaxVertex];  // 入度 
int value[MaxVertex];  // 存值 
int N;  // 总值
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;   // 定义最小堆 
map<int,int> m;

// 插入边 
void Insert(){
	for(int i=0;i<N;i++){ 
		if(0 <= value[i]){
			m.insert(pair<int,int>(value[i],i));   // 存下标与值的映射关系 
			int remainder = value[i]%N;  // 余数 
			if(remainder==i)
				Indegree[i] = 0;
			else if(remainder != i){
				Indegree[i] = (i - remainder < 0)?(i - remainder + N):(i - remainder);
				for(int j=remainder;j!=i;j=(j+1)%N)
					G[j][i] = 1;
			}
		}
	}
}

// 初始化图 
void build(){
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			G[i][j] = INF;
	Insert();
}

// 拓扑排序 
void TopSort(){
	for(int i=0;i<N;i++)
		if(!Indegree[i] && 0 < value[i])
			q.push(value[i]);
	bool flag = true;
	while(!q.empty()){
		int tmpValue = q.top(); 
		int v = m[tmpValue];  // 找回下标 
		q.pop();
		if(flag)
			flag = false;
		else
			cout<<" ";
		cout<<tmpValue;
		for(int w=0;w<N;w++)
			if(G[v][w]!=INF){  // 如果连通 
				if(--Indegree[w]==0)
					q.push(value[w]);
			}
	}
}


int main(){
	cin>>N;
	int i=0;
	for(int i=0;i<N;i++)
		cin>>value[i];
	build();

	TopSort();
	return 0;
}