C++ 酒店房间分配问题：最小化客人愤怒值 - 算法详解 - 常规

C++ 酒店房间分配问题：最小化客人愤怒值 - 算法详解

问题描述

小 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

解题思路

为了最小化所有客人的愤怒值之和，我们可以采用以下策略：

使用数组模拟环形房间： 使用一个大小为 m 的数组 rooms 来表示酒店房间，数组下标对应房间编号。
遍历客人分配房间： 逐个遍历客人，将他们分配到房间。
统计房间占用情况： 对于每个客人，我们将他分配到的房间以及相邻房间的占用情况进行统计。
计算愤怒值： 根据统计结果，我们可以计算出每个客人的愤怒值。
总愤怒值： 将所有客人的愤怒值相加，即为所有客人的愤怒值之和。

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> rooms(m, 0); // 使用数组模拟环形房间
    int ans = 0; // 存储所有客人的愤怒值之和

    for (int i = 0; i < n; i++) {
        int room;
        cin >> room;
        rooms[room - 1]++; // 将客人分配到房间，房间占用情况+1

        // 处理环形房间的相邻房间
        if (room == 1) {
            rooms[m - 1]++;
        } else {
            rooms[room - 2]++;
        }
    }

    // 计算每个客人的愤怒值并累加
    for (int i = 0; i < m; i++) {
        if (rooms[i] > 1) {
            ans += rooms[i] - 1;
        }
    }

    cout << ans << endl;
    return 0;
}

代码解析

初始化： 使用 vector<int> rooms(m, 0) 创建一个大小为 m 的数组 rooms，并初始化所有元素为 0，表示所有房间都空闲。
分配房间： 遍历所有客人，对于每个客人，读取他的房间号 room，并将 rooms[room - 1] 加 1，表示该房间被占用。
处理相邻房间： 由于房间是环形排列，需要额外判断房间号为 1 和其他情况，分别处理相邻房间的占用情况。
计算愤怒值： 遍历 rooms 数组，对于每个房间，如果 rooms[i] > 1，说明该房间有超过 1 个客人，此时该房间的客人会产生 rooms[i] - 1 点愤怒值。
输出结果： 将所有客人的愤怒值之和 ans 输出。

优化

在上述代码中，我们使用了 vector 容器来模拟环形房间。为了提高效率，可以使用数组来代替 vector，因为数组访问元素的速度更快。

总结

本文详细讲解了如何使用 C++ 代码解决酒店房间分配问题，目标是将 n 位客人分配到 m 间环形房间中，使所有客人产生的愤怒值之和最小。文章包含问题描述、解题思路、代码实现及示例，并对代码进行了优化和注释，便于读者理解。