AcWing 1638. 哈希 - 平均查找时间
原题链接
简单
作者:
aac
,
2024-11-24 14:38:07
,
所有人可见
,
阅读 2
N = int(1e4 + 10)
hash = [0] * N
def is_prime(x):
if x < 2:
return False
for i in range(2,int(x ** 0.5) + 1):
if x % i == 0:
return False
return True
def find(x): # 一个函数完成两个功能,x所在下标和查找的时间
start = x % m_size
for i in range(m_size):
k = (start + i * i) % m_size
if hash[k] == x or hash[k] == 0:
return (k,i + 1)
return (-1,m_size + 1)
m_size,n,m = map(int,input().split())
while not is_prime(m_size):
m_size += 1
for x in map(int,input().split()):
t = find(x)
if t[0] == -1:
print(f'{x} cannot be inserted.')
else:
hash[t[0]] = x
res = 0
for x in map(int,input().split()):
res += find(x)[1]
print(f'{res / m:.1f}')