酒店安排-最小愤怒值

酒店安排 - 最小愤怒值

小 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 个节点的问题。每个节点代表一个客人，插入节点的位置代表客人的房间位置。

接下来，我们可以使用贪心算法来解决这个问题。贪心算法的思路是，每次插入节点时，选择与周围节点相邻但无人的位置插入。这样可以保证每次插入节点时，愤怒值最小。

C++ 代码实现

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> rooms(m + 1, 0); // 初始化房间状态，0表示空
    int anger = 0; // 总愤怒值

    for (int i = 0; i < n; i++) {
        int position = 1; // 客人要插入的位置

        // 寻找与周围房间都无人的位置插入客人
        while (rooms[position] || rooms[(position % m) + 1]) {
            position++;
        }

        rooms[position] = 1; // 将该位置设为有人
        anger += rooms[(position % m) + 1]; // 更新愤怒值
    }

    cout << anger << endl;

    return 0;
}