PAT 1145. 哈希 - 平均查找时间
原题链接
简单
作者:
YAX_AC
,
2024-11-14 19:30:20
,
所有人可见
,
阅读 2
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10010;
int s,n,m;
int h[N];
bool is_prime(int x)
{
if(x==1) return 0;
for(int i = 2; i*i<=x; i++)
if(x%i==0) return 0;
return 1;
}
int find(int x,int &cnt)
{
int t = x % s;
cnt = 1;
for(int k = 0; k<s; k++,cnt++)
{
int i = (t+k*k)%s;
if(!h[i] || h[i]==x) return i;
}
return -1;
}
int main()
{
cin>>s>>n>>m;
while(!is_prime(s)) s++;
for(int i = 0; i<n; i++)
{
int x,count;
cin>>x;
int t = find(x,count);
if(t==-1) printf("%d cannot be inserted.\n",x);
else h[t] = x;
}
int cnt = 0;
for(int i = 0; i<m; i++)
{
int x,count;
cin>>x;
find(x,count);
cnt += count;
}
printf("%.1lf\n",(double)cnt/m);
return 0;
}