PAT 1145 Hashing - Average Search Time

个人学习记录，代码难免不尽人意。

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table first. Then try to find another sequence of integer keys from the table and output the average search time (the number of comparisons made to find whether or not the key is in the table). The hash function is defined to be H(key)=key%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.

Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.

Input Specification:
Each input file contains one test case. For each case, the first line contains 3 positive numbers: MSize, N, and M, which are the user-defined table size, the number of input numbers, and the number of keys to be found, respectively. All the three numbers are no more than 10 4 . Then N distinct positive integers are given in the next line, followed by M positive integer keys in the next line. All the numbers in a line are separated by a space and are no more than 10 5 .

Output Specification:
For each test case, in case it is impossible to insert some number, print in a line X cannot be inserted. where X is the input number. Finally print in a line the average search time for all the M keys, accurate up to 1 decimal place.

Sample Input:
4 5 4
10 6 4 15 11
11 4 15 2
Sample Output:
15 cannot be inserted.
2.8

#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10010;
int hashtable[maxn];
bool isprime(int n){if(n<=1) return false;int mid=(int)sqrt(1.0*n);for(int i=2;i<=mid;i++){if(n%i==0) return false;}return true;
}
int findnextprime(int n){int newn=n+1;while(true){if(isprime(newn)){break;}else newn++;}return newn;
} 
int main(){int msize,n,m;scanf("%d %d %d",&msize,&n,&m);if(!isprime(msize))msize=findnextprime(msize);fill(hashtable,hashtable+msize,0);vector<int> v;for(int i=0;i<n;i++){int a;scanf("%d",&a);bool flag=false;for(int j=0;j<=msize;j++){if(hashtable[(a+j*j)%msize]==0){hashtable[(a+j*j)%msize]=a;flag=true;break;}}if(!flag) v.push_back(a);}if(!v.empty()){for(int i=0;i<v.size();i++){printf("%d cannot be inserted.\n",v[i]);}}int sum=0;for(int i=0;i<m;i++){int a;scanf("%d",&a);for(int j=0;j<=msize;j++){if(hashtable[(a+j*j)%msize]==a||hashtable[(a+j*j)%msize]==0){sum++;break; }sum++; }}printf("%.1lf\n",(double)sum/m); 
}

这道题对于不熟悉hash的人真的是痛苦！但是也有解决办法！
我们需要提前了解平方探测法，和一个核心逻辑：如果在查找时对应位置上为空，那么就不用再往后查找了，这个可能看起来很“蠢”，但是确实很容易忽视。
初次之外，还需要知道需要最多需要查找几次，我们可以很容易得到（具体证明另外搜索）：最多Msize次。很简单，因为在Msize+1次时，（a+Msize*Msize）%Msize=a，所以msize+1次和第一次是相同的结果，不需要再搜了。
下面就是这道题最让我迷惑的地方，题目给了样例结果是2.8，也就是说4个数对比次数总和是11，4个数只有15一直查找到了最后，结果我们推得15查找了6次，这就和我们上面得到的结果不一样，所以我改成了for(int j=0;j<=msize;j++)就通过了。

这道题告诉我们，如果一道题没有一点思路，尽量从给的样例输入和输出上下手，试图还原整个过程，总会有一点思路的。