?
本题目有set和并查集两种做法。
其实这个题目和18770非常相似，当计算出a[i]的哈希值y=H（a[i]）时，如果y是空的，那么将a[i]存放在y位置，不然就向后进行线性探测。换句话说找到大于等于y的还没使用过的最小值。因为凡是使用过的位置都无法再次使用，可以理解为将其删除掉。
解题思路：先将存储位置0,1,......n-1放入一个set集合，每次对哈希结果y进行查找，如果没有大于等于y的值，那么选择最小值。题目另一个要求输出不冲突的元素数量，如果在set中找到的位置等于y就是不冲突。
通过本题可以看出，哈希表线性探测过程也可以进行优化。
#include <iostream>
#include <set>
typedef long long ll;
using namespace std;
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,j,n,x,y,hs[100005],cnt=0;
set<int>s;
cin>>n;
for(i=0;i<n;i++) /**< 先把n个位置下表送入set */
s.insert(i);
for(i=1;i<=n;i++)
{
cin>>x;
y=x%n;
set<int>::iterator it=s.lower_bound(y);
if(it==s.end())/**< 如果没有大于等于y的位置，那么选择最小值 */
it=s.begin();
if(y==*it)/**< 不冲突 */
cnt++;
hs[*it]=x; /**< *it就是选中的存储位置 */
s.erase(it);/**< 用过的位置要删除 */
}
cout<<cnt<<endl;
for(i=0;i<n;i++)
cout<<hs[i]<<' ';
return 0;
}
赠送一个并查集的写法：并查集的思想是，当我们使用了y位置，那么通过将y和y+1进行并操作，使得后面再查询y位置时，得到的结果时y+1的位置。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,a[1000005],f[1000005],ans=0;
int findx(int x)
{
return x==f[x]?x:f[x]=findx(f[x]);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,j,x;
cin>>n;
for(i=0;i<n;i++)
f[i]=i;
for(i=1;i<=n;i++)
{
cin>>x;
int x1=findx(x%n),x2=findx((x1+1)%n);/**< 待插入的下一个位置x2 */
if(x1==x%n)
ans++;
a[x1]=x;
f[x1]=x2;
}
cout<<ans<<endl;
for(i=0;i<n;i++)
cout<<a[i]<<' ';
return 0;
}
