Data Structures and Algorithms (English) - 7-18 Hashing - Hard Version(30 分)

简介: Data Structures and Algorithms (English) - 7-18 Hashing - Hard Version(30 分)

题目链接:点击打开链接

 

题目大意:利用线性探测冲突建立Topo图,用Topo排序输出(多个 in[i]==0,输出结点值较小的那个)。

image.png解题思路:关键在于建Topo图遇到冲突时,不是一开始建造的时候位置都为空,而是一开始的时候位置就是Input的位置已经占着了的,以后者规则为基准。因为 int 值可能很大,所以使用 unordered_map 来替换。

如题目中的样例,假设题目中的元素在一个ha[11]的数组中


33 % 11 = 0,ha[0] = 33 ,因此什么事都不做;


1 % 11 = 1,ha[1] = 1, 同上;


13 % 11 = 2,ha[2] = 13, 同上;


12 % 11 = 1,ha[1] != 12,说明发生了冲突,此时1和13一定在12之前进入哈希表(因为线性探测法是逐个向后找空位),所以建立<1,12>、<13, 12>这两条有向边来表明先后顺序;


……// 后面的都类似;


而32 % 11 = 10,ha[10] != 32,又发生了冲突,而此时已经是表的末尾,因此只能重新回到0号位依次探测空位直到8号位,因此需要建立<21, 32>、<33, 32>、<1, 32>...<22, 32>这些有向边


以上步骤是根据哈希表来建立一个有向图。其中建立有向图时,结点我选择的是用下标来表示(因为不知道元素的大小),不过还是用了个 unordered_map 数组来记录下标。


然后就是根据有向图来做一个拓扑排序,排序的时候使用优先队列容器来存储入度为0的元素,方便找到最小的元素。


AC 代码

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintmaxn=1009;
intn;
intha[maxn], in[maxn], g[maxn][maxn];
unordered_map<int,int>ump, id;
vector<int>vec;
priority_queue<int,vector<int>,greater<int>>pq;
voidtopo()
{
for(inti=1;i<=n;i++)
if(in[i]==0&&ump[i]>=0) pq.push(ump[i]); // avoid 负数的情况while(!pq.empty())
    {
inttp=pq.top(); pq.pop();
vec.push_back(tp);
for(inti=1;i<=n;i++)
if(g[id[tp]][i] &&--in[i]==0)
pq.push(ump[i]);
    }
}
intmain()
{
intnum,p,pos;
scanf("%d",&n);
p=n;
for(inti=1;i<=n;i++)
    {
scanf("%d",&num);
ump[i]=num;
id[num]=i;
ha[i-1]=i;
    }
for(inti=1;i<=n;i++)
    {
if(ump[i]<0) continue;
for(intj=0;;j++)
        {
pos=(ump[i]+j)%p;
if(ha[pos]==i||ump[ha[pos]]<0) break;
g[ha[pos]][i]=1;
in[i]++;
        }
    }
topo();
for(inti=0;i<vec.size();i++)
printf("%d%c",vec[i],i==vec.size()-1?'\n':' ');
return0;
}
目录
相关文章
|
机器学习/深度学习 算法
Data Structures and Algorithms (English) - 7-28 Review of Programming Contest Rules(30 分)
Data Structures and Algorithms (English) - 7-28 Review of Programming Contest Rules(30 分)
209 0
Data Structures and Algorithms (English) - 7-28 Review of Programming Contest Rules(30 分)
Data Structures and Algorithms (English) - 7-11 Saving James Bond - Hard Version(30 分)
Data Structures and Algorithms (English) - 7-11 Saving James Bond - Hard Version(30 分)
176 0
Data Structures and Algorithms (English) - 7-8 File Transfer(25 分)
Data Structures and Algorithms (English) - 7-8 File Transfer(25 分)
110 0
Data Structures and Algorithms (English) - 6-8 Percolate Up and Down(20 分)
Data Structures and Algorithms (English) - 6-8 Percolate Up and Down(20 分)
103 0
Data Structures and Algorithms (English) - 6-15 Iterative Mergesort(25 分)
Data Structures and Algorithms (English) - 6-15 Iterative Mergesort(25 分)
186 0
Data Structures and Algorithms (English) - 7-9 Huffman Codes(30 分)
Data Structures and Algorithms (English) - 7-9 Huffman Codes(30 分)
100 0
Data Structures and Algorithms (English) - 7-10 Saving James Bond - Easy Version(25 分)
Data Structures and Algorithms (English) - 7-10 Saving James Bond - Easy Version(25 分)
92 0
Data Structures and Algorithms (English) - 7-12 How Long Does It Take(25 分)
Data Structures and Algorithms (English) - 7-12 How Long Does It Take(25 分)
110 0
Data Structures and Algorithms (English) - 6-13 Topological Sort(25 分)
Data Structures and Algorithms (English) - 6-13 Topological Sort(25 分)
109 0
Data Structures and Algorithms (English) - 6-7 Isomorphic(20 分)
Data Structures and Algorithms (English) - 6-7 Isomorphic(20 分)
124 0