PAT甲级1145.

目录

A1145

题目

样例

输入:

4 5 4
10 6 4 15 11
11 4 15 2

输出:

15 cannot be inserted.
2.8

思路和坑点

　　思路:
　　首先，要进行哈希表的构建，哈希的长度为不小于tsize的一个素数。构建哈希表的时候，使用正的平方探测法解决冲突问题。
　　然后，根据构建好的哈希表进行查找，查找结束的标志为，查找到或者查找到空位、或者回到原位。

AC代码

#include<bits/stdc++.h>
using namespace std;
bool isprime(int n){                    //判断是不是素数
    for(int i=2;i*i<=n;i++)
        if(n%i==0)  return false;
    return true;
}
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int tsize,n,m,a;
    scanf("%d%d%d",&tsize,&n,&m);
    while(!isprime(tsize)) tsize++;     //找到不小于tsize的素数作为哈希表的长度
    vector<int> v(tsize,0);             //全部初始化为0 ，表示为空位（因为插入的数字都是正数），哈希表 
    for(int i=0;i<n;i++){
        scanf("%d",&a);                 //读入一个数字
        int flag=0;                     //标记是否放入，1为放入，0为未放入
        for(int j=0;j<tsize;j++){       //j为0时表示第一次散列，之后表示二次探测 
            int pos=(a+j*j)%tsize;
            if(v[pos]==0){              //如果找到空位，则插入a并修改标记
                v[pos]=a;
                flag=1;
                break;
            } 
        } 
        if(flag==0) 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;//找到或到达空位，或者j增量取到tsize时回到第一次散列的位置时，结束查找 
        }
    } 
    printf("%.1lf\n",ans*1.0/m);        //输出平均查找次数
    return 0;    
}