PAT甲级1078.

目录

A1078

题目

样例

输入:

4 4
10 6 4 15

输出:

0 1 4 -

思路和坑点

　　使用hash函数直接进行hash运算，如果不成功则进行正的二次探测。

AC代码

#include<bits/stdc++.h>
using namespace std;
bool isprimer(int x){                        //素数判别函数 
    if(x<=1) return false;
    for(int i=2;i<=(int)sqrt(x*1.0);i++){
        if(x%i==0)
            return false;
    }
    return true;
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int size,n;
    scanf("%d%d",&size,&n); 
    while(!isprimer(size))                      //找到一个符合条件的素数作为hash表的大小 
        size++;
    vector<bool> Table(size,false);             //hash表的标记，当前下标位置是否已被分配，初始化为false 
    for(int i=0;i<n;i++){
        if(i) putchar(' ');                     //出了第一个不输出空格以外，之后的都输出空格 
        int num;
        scanf("%d",&num);                       //读入一个数字 
        int pos=num%size;
        if(Table[pos]==false){                  //如果hash表中直接可分配位置，则分配，并修改标记 
            printf("%d",pos);
            Table[pos]=true;
        }
        else {                                  //否则，使用二次探测法 
            int step;                           //探测步长 
            for(step=1;step<size;step++){       //探测步长最大为hash表长 
                pos=(num+step*step)%size;       //计算探测位置 
                if(Table[pos]==false){          //如果可以分配则分配，并修改标记 
                    printf("%d",pos);
                    Table[pos]=true;
                    break;
                }
            }
            if(step>=size) putchar('-');        //如果二次探测失败，则输出- 
        }
    }
    return 0;
}