uicccui
2021-11-10 18:34
采纳率: 42.9%
浏览 47

数据结构与算法“爸爸去哪儿”分配问题1

题目描述

最近“爸爸去哪儿”节目很火,据说新一期节目分房的策略有所改变:共有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间房:

img

平均查找长度为:(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.400

给出代码,谢谢

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

2条回答 默认 最新

查看更多回答(1条)

相关推荐 更多相似问题