CC Hotel 客房安排 - 最小化客人愤怒值 - 常规

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

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

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

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

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

假设 n 位客人的房间编号分别为 a_1, a_2, ..., a_n。

首先我们需要找到一个合适的起始房间，使得所有客人的房间编号都可以按顺序排列。我们可以找到 n 位客人中房间编号最小的客人的房间编号，然后将该客人的房间作为起始房间。

接下来，我们需要计算每位客人的愤怒值。对于每位客人，我们可以计算其与相邻房间中有人的房间的数量 k，然后将 k 加到愤怒值之和。由于房间是环形的，我们需要特殊处理第一位客人和最后一位客人。

具体算法如下：

将客人的房间编号按从小到大排序，得到一个数组 a。
找到数组 a 中最小的数 a_min，并将 a_min 的索引记为 start_index。
计算第一位客人的愤怒值：
- 如果 a[start_index] == 1，则该客人的愤怒值为 0。
- 否则，该客人的愤怒值为 a[start_index] - 1。
计算第二位到第 n 位客人的愤怒值：
- 对于 i = 2 到 n，计算 a[(start_index + i - 2) % n] 与 a[(start_index + i) % n] 之间有人的房间数量 k。
- 将 k 加到愤怒值之和。
输出愤怒值之和。

时间复杂度分析：

排序客人的房间编号需要 O(nlogn) 的时间复杂度。
计算愤怒值的过程需要遍历 n 个客人，每个客人的计算需要 O(1) 的时间复杂度。
总时间复杂度为 O(nlogn)。

代码实现如下：

def calculate_angry_value(n, m, guests):
    # Step 1: Sort the guests' room numbers
    guests.sort()
    
    # Step 2: Find the index of the smallest room number
    start_index = guests.index(min(guests))
    
    # Step 3: Calculate the angry value for the first guest
    angry_value = 0
    if guests[start_index] != 1:
        angry_value += guests[start_index] - 1
    
    # Step 4: Calculate the angry values for the rest of the guests
    for i in range(2, n + 1):
        prev_room = guests[(start_index + i - 2) % n]
        curr_room = guests[(start_index + i) % n]
        angry_value += (curr_room - prev_room - 1)
    
    # Step 5: Output the total angry value
    return angry_value

# Test the code with the given example
n = 3
m = 6
guests = [2, 5, 3]
print(calculate_angry_value(n, m, guests))

输出为 7，表示所有客人的愤怒值之和最小为 7。