【1145】Hashing - Average Search Time (25分)【hash 平方探测法】

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//插入时pos = (a + j * j) % tsize，j是从0～tsize-1的数字
//查询时pos = (a + j * j) % tsize，其中j <= tsize
bool isprime(int n){//判断是否是素数
  for(int i=2;i*i<=n;i++){
    if(n%i==0)  return false;
  }
  return true;
}
int main(){   
    int tsize,n,m,a;//表长，要插入个数，查询个数
    scanf("%d %d %d",&tsize,&n,&m);
    while(!isprime(tsize))  tsize++;//大于表长的最大素数
    vector<int>v(tsize);
    for(int i=0;i<n;i++){
      scanf("%d",&a);
      int flag=0;
      for(int j=0;j<tsize;j++){
        int pos=(a+j*j)%tsize;
        if(v[pos]==0){
          v[pos]=a;
          flag=1;
          break;
        }
      }
      if(!flag) printf("%d cannot be inserted.\n",a);
    }
    int ans=0;
    for(int i=0;i<m;i++){
      scanf("%d",&a);
      for(int j=0;j<=tsize;j++){
        ans++;
        int pos=(a+j*j)%tsize;
        if(v[pos]==a||v[pos]==0) break;
        //找到或者没找到(不存在)都退出
      }
    }
    printf("%.1lf\n",ans*1.0/m);
    system("pause");
    return 0;
}