uicccui 2021-11-10 18:30 采纳率: 42.9%
浏览 82
已结题

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

题目描述

最近“爸爸去哪儿”节目很火,据说新一期节目分房的策略有所改变:共有m间房,序号从0到m-1,村长根据每个小朋友的英 文名来分配房子。

具体规则如下:

每个小朋友的英文名都能得到一个对应的数值:‘a’数值为1,‘b’数值为2,…,‘z’数值为26,小朋友的英文名的数值为各个字母的数值和,比如kimi的英文名的数值为11+9+13+9=42。注:规定输入的英文名均为小写字母

假设小朋友的英文名的数值为numName的话,那这个小朋友和他爸爸本期节目要住的房子就是(numName mod m)号房。
如果某小朋友的numName mod m得到的值和之前的小朋友的一样,则用哈希中的平方探测法。

分配完房子之后,村长想知道这个分房策略的平均查找长度是多少,也就是说村长根据这个策略来查找每个人的房子时,平均
需要查找多少房子(结果保留三位小数)。

比如有以下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

给出代码,谢谢

  • 写回答

1条回答 默认 最新

  • 广大菜鸟 2021-11-10 20:33
    关注
    
    #include<iostream>
    using namespace std;
    int house[10000] = { 0 };
    int nameToInt(string name) {
        int res = 0;
        for (char c : name) {
            res += (c - 'a') + 1;
        }
        return res;
    }
    int nextValue(int v, int tryTime) {
      /*  int n = tryTime / 2;
        int sign = tryTime % 2 == 0 ? 1 : -1;
        int add = n + 1;
        return v + sign * add * add;*/
        int add = tryTime + 1;
        return v + add * add;
    }
    string residents[10000];
    int main() {
        int n, m, i, pathLength, tryTime = 0;
        int value, oldvalue, newValue;
        string name;
        // n: 人数,m:房间
        while (cin >> n >> m) {
            i = value = 0;
            pathLength = 0;
            while (i++ < n) {
                cin >> name;
                value = nameToInt(name) % m;
                pathLength += 1;
                if (house[value]) {
                    tryTime = 0; oldvalue = value;
                    while (house[value]) {
                        // 增量:+1 -1 +2^2 - 2^2 ...
                        newValue = nextValue(oldvalue, tryTime);
                        while (newValue < 0) {
                            newValue += m;
                        }
                        value = (newValue) % m;
                        //value = (value + 1) % m;
                        pathLength += 1;
                        tryTime += 1;
                        if (tryTime > m) exit(-1);//全满
                    }
                }
                residents[value] = name;
                house[value] = 1;
            }
            memset(house, 0, sizeof(int) * m);
            for (i = 0; i < m; i++) {
                cout << i << ":" << (residents[i] != "" ? residents[i] : "NULL") << endl;
                residents[i] = "";
            }
            printf("%.3lf\n", (1.0 * pathLength / (1.0 * n)));
        }
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 11月18日
  • 已采纳回答 11月10日
  • 修改了问题 11月10日
  • 创建了问题 11月10日