題干：

鏈接：https://ac.nowcoder.com/acm/contest/1080/B
來源：牛客網
?

tokitsukaze有n個數，需要按順序把他們插入哈希表中，哈希表的位置為0到n-1。

插入的規則是：
剛開始哈希表是空的。
對于一個數x，在哈希表中，如果(x mod n)的位置是空的，就把x放在(x mod n)的位置上。如果不是空的，就從(x mod n)往右開始找到第一個空的位置插入。若一直到n-1都不是空的，就從位置0開始繼續往右找第一個空的位置插入。

因為哈希表總共有n個空位，需要插入n個數，所以每個數都能被插入。

現在tokitsukaze想知道把這n個數按順序插入哈希表后，哈希表中的每個位置分別對應的是哪個數。

輸入描述:

第一行包含一個正整數n(1≤n≤10^6)。 第二行包含n個非負整數x(0≤x≤10^9)，這些數按從左到右的順序依次插入哈希表。

輸出描述:

輸出一行，n個數，第i個數表示哈希表中位置為i所對應的數。(0≤i≤n-1)

示例1

輸入

復制

4 1 2 6 5

輸出

復制

5 1 2 6

說明

插入1時，1 mod 4=1，是空的，在位置1插入。 插入2時，2 mod 4=2，是空的，在位置2插入。 插入6時，6 mod 4=2，不是空的，找到下一個空的位置為3，所以在位置3插入。 插入5時，5 mod 4=1，不是空的，找到下一個空的位置為0，所以在位置0插入。

示例2

輸入

復制

4 3 0 7 11

輸出

復制

0 7 11 3

說明

插入3時，3 mod 4=3，是空的，在位置3插入。 插入0時，0 mod 4=0，是空的，在位置0插入。 插入7時，7 mod 4=3，不是空的，找到下一個空的位置為1，所以在位置1插入。 插入11時，11 mod 4=3，不是空的，找到下一個空的位置為2，所以在位置2插入。

解題報告：

? ?這題做法不少，可以直接set維護第一個空位，二分查找即可。

? ?還可以用并查集維護空位，每次在x位置插入數后，合并x和(x+1)%n，也不難寫。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e6 + 5; set<int> ss; int ans[MAX]; int main() {int n;cin>>n;for(int i = 0; i<n; i++) ss.insert(i);for(int x,i = 1; i<=n; i++) {scanf("%d",&x);auto it = ss.lower_bound(x%n );if(it == ss.end()) ans[*ss.begin()] = x,ss.erase(ss.begin());else ans[*it] = x,ss.erase(it);}for(int i = 0; i<n; i++) printf("%d%c",ans[i],i == n-1 ? '\n' :' ');return 0 ; }

附一個并查集代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e6 + 5; int f[MAX]; int getf(int v) {return f[v] == v ? v : f[v] = getf(f[v]); } void merge(int u,int v) {int t1 = getf(u),t2 = getf(v);f[t1] = t2; } int ans[MAX]; int main() {int n;cin>>n;for(int i = 0; i<=n; i++) f[i] = i;for(int x,i = 1; i<=n; i++) {scanf("%d",&x);int pos = x%n;int fa = getf(pos);ans[fa] = x;merge(fa,(fa+1)%n);}for(int i = 0; i<n; i++) printf("%d%c",ans[i],i == n-1 ? '\n' : ' ');return 0 ; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 1080B】tokitsukaze and Hash Table（STLset，并查集，Hash）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。