题目链接
题意
这道题是给出一个散列表，根据散列表逆推出插入的数的最小字典序的排列。
我们观察一下散列表，我们就发现每一个数离应该插的位置(x mod key)到放置的当前位置的所有的数一定比这个数先放，然后我们可以得出一个关系，我们假设对每个数都成立这个关系，那么我们可以得到一个有向无环图，然后我们就可以得出拓扑序，是满足该题目要求的序列，题目为了保证唯一性，要求满足要求的最小字典序，所以我们就贪心求最小拓扑序。
代码
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_map>using namespace std ;const int N = 1e6 + 10 ;int hp[N] ;
int h[N] , e[N] , ne[N] , idx ;
unordered_map<int , int> d ;
priority_queue<int , vector<int> , greater<int>> q ;
int hh , tt , n ;
int ans[N] , cnt ;void add(int a , int b)
{
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;d[b] ++ ;
}void bfs()
{
for(int i = 0 ; i < n ; i ++)if(~hp[i]){
int x = hp[i] ;if(!d[x]) q.push(x) ;}while(q.size()){
int t = q.top() ;q.pop() ; ans[++ cnt] = t ;for(int i = h[t] ; ~i ; i = ne[i]){
int ver = e[i] ;d[ver] -- ;if(!d[ver]) q.push(ver) ;}}for(int i = 1 ; i <= cnt ; i ++){
printf("%d" , ans[i]) ;if(i != cnt) printf(" ") ;}
}int main(void)
{
memset(h , -1 , sizeof h) ;scanf("%d" , &n) ;for(int i = 0 ; i < n ; i ++)scanf("%d" , &hp[i]) ;for(int i = 0 ; i < n ; i ++){
if(hp[i] == -1) continue ;int x = hp[i] ;int k = x % n ;if(k == i) continue ;for(int j = k ; j != i ; j = (j + 1) % n)if(hp[j] != -1)add(hp[j] , x) ;} bfs() ;
}