Home PAT 1145 Hashing - Average Search Time
Post
Cancel

PAT 1145 Hashing - Average Search Time

Link

(正向的) 平方探测法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int len,n,m,a,num[100010];
bool isPrime(int x){
    if(x==1) return false;
    for(int i=2;i*i<=x;++i)
        if(x%i==0) return false;
    return true;
}
int main() {
    scanf("%d%d%d",&len,&n,&m);
    if(!isPrime(len))
        do{len++;}while(!isPrime(len));
    vector<int>b(len,0);
    for(int i=1;i<=n;++i){
        scanf("%d",&a);
        int j=0;
        while(j<len&&b[(a+j*j)%len]) j++;
        if(!b[(a+j*j)%len]) b[(a+j*j)%len]=a;
        else printf("%d cannot be inserted.\n",a);
    }
    double ans=0.0;
    for(int i=1;i<=m;++i){
        scanf("%d",&a);
        int j=0;
        while(j<=len&&b[(a+j*j)%len]!=a&&b[(a+j*j)%len]!=0) j++;
        ans+=j;
        if(j<=len) ans++;
    }
    ans/=m;
    printf("%.1lf\n",ans);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.