逆散列问题

给定长度为 N 的散列表，处理整数最常用的散列映射是 H(x)=x%N。如果我们决定用线性探测解决冲突问题，则给定一个顺序输入的整数序列后，我们可以很容易得到这些整数在散列表中的分布。例如我们将 1、2、3 顺序插入长度为 3 的散列表HT[]后，将得到HT[0]=3，HT[1]=1，HT[2]=2的结果。

但是现在要求解决的是“逆散列问题”，即给定整数在散列表中的分布，问这些整数是按什么顺序插入的？

输入格式：

输入的第一行是正整数 N（≤1000），为散列表的长度。第二行给出了 N 个整数，其间用空格分隔，每个整数在序列中的位置（第一个数位置为0）即是其在散列表中的位置，其中负数表示表中该位置没有元素。题目保证表中的非负整数是各不相同的。

输出格式：

按照插入的顺序输出这些整数，其间用空格分隔，行首尾不能有多余的空格。注意：对应同一种分布结果，插入顺序有可能不唯一。例如按照顺序 3、2、1 插入长度为 3 的散列表，我们会得到跟 1、2、3 顺序插入一样的结果。在此规定：当前的插入有多种选择时，必须选择最小的数字，这样就保证了最终输出结果的唯一性。

输入样例：

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

输出样例：

1 13 12 21 33 34 38 27 22 32

题解：

调试了好几次才模拟成功ORZ。

模拟线性探测方式

当前数字输出的条件是 从该数字线性探测起始位置开始，直到该数字正确位置之间的所有数字都已被输出。

设置标记数组 st[] 记录检测成功的数字。

直接把数据加到优先队列 pq1中，循环检测队首元素，不成功加入到pq2. 成功直接加入输出数组并修改标记。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;

const int N = 1e6;

vector<int> arr, res;
priority_queue<int, vector<int>, greater<int>> pq1, pq2; //总搞混``小顶堆用greater

int n;
bool st[N];

bool check(int x) {
    bool good = false;
    int k = x % n;
    if (arr[k] == x)
    {
        good = true;
        st[x] = true;
    }
    else if (st[arr[k]])
    {
        int k2 = (k + 1) % n;       //向后探测
        while (k2 != k)             //从k+1开始转一圈后退出
        {
            if (arr[k2] != x && !st[arr[k2]]) break;

            if (arr[k2] == x)
            {
                good = true;
                st[x] = true;
                break;
            }
            else if (arr[k2] != x && st[arr[k2]])
                k2 = (k2 + 1) % n;
        }
    }

    return good;
}

int main() {

    cin >> n;
    arr.resize(n);
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        arr[i] = a;
        if (a >= 0) pq1.push(a);
    }
    bool  pushpq2 = false;
    while (!pq1.empty() || !pq2.empty())
    {
        if (pushpq2)
        {
            while (!pq2.empty())
            {
                int temp = pq2.top();
                pq2.pop();
                pq1.push(temp);
            }

        }
        bool good;
        int now = pq1.top();
        pq1.pop();

        good = check(now);
        if (good)
        {
            res.push_back(now);
            pushpq2 = true;
        }
        else
        {
            pq2.push(now);
            pushpq2 = false;
        }

    }

    for (int i = 0; i < res.size(); i++)
    {
        if (i == 0) cout << res[0];
        else cout << ' ' << res[i];
    }

    return 0;
}