CC Hotel 房间分配问题 - 最小愤怒值算法

小 C 开了一家酒店，叫做 CC Hotel。

一天，CC Hotel 来了 n 位客人。小 C 需要把他们都安排在酒店的某一层中。每个房间中只能安排一位客人。

这一层共有 m 间房间，这 m 间房间都是空的，且这 m 间房间形成了一个环形，即对于所有的 1≤x≤m，都有第 x 间房间与第 ((x mod m)+1) 间房间相邻，第 ((x mod m)+1) 间房间与第 x 间房间相邻，其中 x mod m 表示 x 除以 m 得到的余数。

这 n 位客人都十分挑剔，他们希望与自己的房间相邻的房间中没有人。对于某一位客人，若与他的房间相邻的房间中，有 k 间房间有人，则这位客人会产生 k 点愤怒值。

你需要帮助小 C 安排房间，使得所有客人的愤怒值之和最小，并输出所有客人的愤怒值之和的最小值。

输入格式

两个整数 n,m。

输出格式

一个整数，表示所有客人的愤怒值之和的最小值。

输入输出样例

输入 #1 3 5

输出 #1 2

输入 #2 1 4

输出 #2 0

思路

首先，我们可以将问题转化为一个排列问题，即将 n 个客人按照某种顺序分配到 m 个房间中。

为了使愤怒值之和最小，我们需要尽量减少每个客人与其相邻房间中有人的情况。假设我们将 n 个客人按照某种顺序分配到 m 个房间中，我们可以计算出每个客人的愤怒值。

对于第 i 个客人，若其房间的左右相邻房间都没有人，则愤怒值为 0；若左右相邻房间中有一间有人，则愤怒值为 1；若左右相邻房间中都有人，则愤怒值为 2。

我们可以通过遍历所有可能的客人分配方式，计算出每种分配方式下的愤怒值之和，并取最小值作为答案。

实现

具体实现时，我们可以使用回溯法进行遍历。首先，我们可以定义一个长度为 m 的数组 rooms，用来记录每个房间是否有人。初始时，所有房间都为空。

然后，我们从第一个客人开始，依次尝试将其分配到每个房间中。对于每个房间，我们可以判断它的左右相邻房间中是否有人，从而计算出当前客人的愤怒值。然后，我们更新房间的状态，将当前客人分配到房间中，并递归地处理下一个客人。在递归的过程中，我们需要记录当前的愤怒值之和，并不断更新最小值。

具体的伪代码如下：

int minAnger = INT_MAX;  // 初始化愤怒值之和的最小值为一个较大的值

void backtrack(vector<int>& rooms, int n, int m, int currAnger) {
    // 当前客人的索引为 n
    // 当前愤怒值之和为 currAnger
    
    // 所有客人都已经分配完毕
    if (n == 0) {
        minAnger = min(minAnger, currAnger);
        return;
    }
    
    // 尝试将第 n 个客人分配到每个房间中
    for (int i = 0; i < m; i++) {
        // 判断当前房间的左右相邻房间是否有人
        bool left = rooms[(i-1+m) % m];
        bool right = rooms[(i+1) % m];
        
        // 计算当前客人的愤怒值
        int anger = (left ? 1 : 0) + (right ? 1 : 0);
        
        // 更新房间状态，将当前客人分配到房间中
        rooms[i] = 1;
        
        // 递归处理下一个客人
        backtrack(rooms, n-1, m, currAnger + anger);
        
        // 恢复房间状态
        rooms[i] = 0;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> rooms(m, 0);  // 初始化房间状态
    
    backtrack(rooms, n, m, 0);  // 从第一个客人开始进行回溯
    
    cout << minAnger << endl;  // 输出愤怒值之和的最小值
    
    return 0;
}

算法复杂度

该算法的时间复杂度是 O(m^n)，其中 n 是客人的数量，m 是房间的数量。由于 n 和 m 均不超过 100，所以该算法是可行的。