11-散列4 Hashing - Hard Version (30 分) 散列表反向思维——用拓扑排序做

- 日理万妓 2024-04-17 06:02 42阅读 0赞

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

**题意：**n为表长，输出目前每个格子里填的数字，负值即为空，问输入的序列是怎么样的

**思路：**其实这是一道拓扑排序的题，根据偏移量建立边的关系

若结点a定位在2，但是他其实在3，说明发生了冲突，这是冲突他的结点必然在他之前输入

顺便重温了一下优先队列，因为存的是下标，所以不能简单的greater<int>，要用cmp哦

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <vector>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    vector<int> v[10005];//单向图 - 存的是下标,不是数值 
    int a[10005];
    int degree[10005];//入度
    struct cmp 
    {
        bool operator()(int i,int j) 
        {
            return a[i]>a[j];
        }
    };
    priority_queue<int,vector<int>,cmp > q;
    int main()
    {
    	int n,i,j,x;
    	memset(degree,0,sizeof degree);
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&a[i]);
    		if(a[i]>=0)
    		{
    			x=a[i]%n;
    			degree[i]=(i+n-x)%n;
    			if(degree[i]!=0)//发生冲突 
    			{
    				for(j=0;j<=degree[i];j++)
    				v[(x+j)%n].push_back(i);	
    			}
    			else
    			q.push(i);
    		}
    	}
    	//for(i=0;i<n;i++)
    	//printf("%d : %d\n",a[i],degree[i]);
    	int f=0;//控制空格输出 
    	while(!q.empty())
    	{
    		int u=q.top();	
    		q.pop();
    		
    		if(f)printf(" ");
    		printf("%d",a[u]);
    		f++;
    			
    		for(i=0;i<v[u].size();i++)
    		{
    			degree[v[u][i]]--;
    			if(degree[v[u][i]]==0)
    			q.push(v[u][i]);
    		}
    	}
    }