题目描述
最近“爸爸去哪儿”节目很火，据说新一期节目分房的策略有所改变:共有m间房，序号从0到m-1，村长根据每个小朋友的英 文名来分配房子。
具体规则如下:
每个小朋友的英文名都能得到一个对应的数值:‘a’数值为1，‘b’数值为2，…，‘z’数值为26，小朋友的英文名的数值为各个字母的数值和，比如kimi的英文名的数值为11+9+13+9=42。注:规定输入的英文名均为小写字母
假设小朋友的英文名的数值为numName的话，那这个小朋友和他爸爸本期节目要住的房子就是(numName mod m)号房。 如果某小朋友的numName mod m得到的值和之前的小朋友的一样，则用哈希中的线性探测法:找下一号房直到找到一间还没有父 子入住的，若已经找到第m-1间还有人，则回到第0间找。
分配完房子之后，村长想知道这个分房策略的平均查找长度是多少，也就是说村长根据这个策略来查找每个人的房子时，平均需要查找多少房子(结果保留三位小数)。
比如有以下5个小朋友，并且有6间房:
平均查找长度为:(1+1+1+2+2) / 5 = 1.400
输入描述
输入有多个测试用例，以EOF结束。
对于每个测试用例，输入分两部分:
第一部分是1行，有两个整数n和m(1<= n, m<=10,000)，中间用空格隔开，n代表有多少对明星父子参加节目，m代表一共 有多少间房
第二部分是n行，每行都是一个小朋友的英文名，小朋友的英文名彼此都不同，且中间没有空格。每个小朋友的英文名不超过 10个字母，且均为小写字母
输出描述
对于每个测试用例，输出m+1行 前m行，每行为房子序号+“:”+要入住的小朋友的英文名，没有人入住则输出房子序号+“:NULL”
第m+1行输出一个数字，表示平均查找长度，保留三位小数
输入样例
5 6
kimi
tiantian
stone
angela
cindy输出样例
0:kimi
1:stone
2:cindy
3:NULL
4:tiantian
5:angela
1.400Yizuodi的答案
#include <iostream>
#include <sstream>
#include <cstdio>
using namespace std;
int ctoi(char c){
return c-'a'+1;
}
int main(){
int n,m;
double findLength=0;
cin>>n;
cin>>m;
string childname[n],housedata[m];
bool housestate[m]={false};
int numName[n],numMod[n];
for (int i = 0; i < n; i++)
{
cin>>childname[i];
numName[i]=0;
for (int j = 0; j < childname[i].size(); j++)
{
numName[i]+=ctoi(childname[i][j]);
}
numMod[i]=numName[i]%m;
}
for (int i = 0; i < n; i++)
{
int j=numMod[i];
++findLength;
if (!housestate[j])//没住人就入住
{
housestate[j]=true;//先把房子占了
stringstream ss;
ss<<j<<":"<<childname[i];
ss>>housedata[j];
}
else{//房子已经有人住了，仿线性探测法寻找未安排入住的
while(true){
++j;
++findLength;
if (j == m)
{
j=0;
}
if (!housestate[j])//没住人就入住
{
housestate[j]=true;
stringstream ss;
ss<<j<<":"<<childname[i];
ss>>housedata[j];
break;
}
}
}
}
for (int i = 0; i < m; i++)
{
if(housestate[i]){
cout<<housedata[i]<<endl;
}
else{
cout<<i<<":NULL"<<endl;
}
}
printf("%.3lf",findLength/n);
}