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

Question

题目描述

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

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

给出代码，谢谢

Answer 1

#include<iostream>
using namespace std;
int house[1000] = { 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;
}
string residents[1000];
int main() {
    int n, m, i, pathLength,tryTime=0;
    int value,oldvalue;
    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])
                house[value] = 1;
            else {
                tryTime = 0;oldvalue=value;
                while (house[value]) {
                    // 增量:+1 -1 +2^2 - 2^2 ...
                    value = nextValue(oldvalue,tryTime)%m;
                    pathLength += 1;
                    tryTime += 1;
                }
            }
            residents[value] = name;
        }
        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)));
    }
}
/*
5 6
kimi
tiantian
stone
angela
cindy
*/