酒店连续房间分配算法设计与GCD约束问题求解咨询

P位朋友抵达酒店，需预订房间。酒店有n个房间按数组线性排列，数组元素代表房间容量。朋友仅考虑连续房间，需满足：

• (a) 设计时间复杂度为O(n*log(n))的算法，找到满足总容量≥P的连续房间的最低预订成本（每间房成本为C）。
• (b) 设计时间复杂度为O(n)的算法解决上述(a)问题。
• (c) 若不考虑成本与容量，定义“美观分配”为连续房间容量的GCD(Greatest Common Divisor)≥常数K，需设计O(n*log(n))时间复杂度的算法，找到最长的符合条件的连续房间序列。假设可调用O(1)时间的GCD黑盒算法。
• (d) 证明(a)(b)中算法的正确性并分析时间复杂度。

我的思路与疑问 #

• 针对(a)，我的思路是将房间容量按降序排序，再用双指针维护当前窗口，计算满足总容量≥P的最小成本，伪代码如下：

Sort(capacities) // O(n log(n))
minCost = infinity
currentSum = 0
left = 0

for right = 0 to n-1:
    currentSum += capacities[right]
    
    while currentSum >= P:
        minCost = min(minCost, (right - left + 1) * C)
        currentSum -= capacities[left]
        left++
        
minCost is the minimum cost of element allocation.

• 针对(b)，我认为可直接用双指针维护原数组的滑动窗口，伪代码如下：

minCost = infinity
currentSum = 0
left = 0

for right = 0 to n-1:
    currentSum += capacities[right]
    
    while currentSum >= P:
        minCost = min(minCost, (right - left + 1) * C)
        currentSum -= capacities[left]
        left++

minCost is the minimum cost of room allocation.

• 对(c)部分存在疑问，不清楚如何结合GCD约束设计O(n*log(n))时间的算法，需要相关帮助。

针对(c)的解决方案 #

利用GCD的单调性性质（连续子数组的GCD只会随着子数组长度增加而不增，且每次变化至少减半），可以在O(n log n)时间内解决问题，具体步骤如下：

1. 核心思路：对每个数组位置i，维护所有以i结尾的连续子数组的GCD值，以及对应子数组的长度。由于每个位置的不同GCD数量最多为O(log a_i)（a_i为当前元素值），整体操作次数可控。

2. 算法伪代码：

max_len = 0
gcd_map = {}  # 键：GCD值，值：对应连续子数组的长度

for num in capacities:
    new_gcd_map = {}
    # 先处理仅包含当前元素的子数组
    current_gcd = num
    if current_gcd >= K:
        new_gcd_map[current_gcd] = 1
        max_len = max(max_len, 1)
    # 处理延续之前子数组的情况
    for g, length in gcd_map.items():
        new_g = gcd(g, num)
        if new_g >= K:
            if new_g in new_gcd_map:
                # 保留更长的子数组长度
                new_gcd_map[new_g] = max(new_gcd_map[new_g], length + 1)
            else:
                new_gcd_map[new_g] = length + 1
            max_len = max(max_len, new_gcd_map[new_g])
    # 更新当前结尾的GCD映射
    gcd_map = new_gcd_map

return max_len

3. 正确性与时间复杂度分析：

• 正确性：算法枚举了所有以每个位置结尾的符合GCD≥K的连续子数组，且对每个GCD值仅保留最长的子数组长度（更长的子数组更可能成为全局最长），不会遗漏任何可能的有效子数组。
• 时间复杂度：每个元素对应的不同GCD数量为O(log a_i)，因为每次计算新GCD时，若值发生变化则至少减半，因此总操作次数为O(n log A)（A为数组最大元素），符合O(n log n)的要求。

内容的提问来源于stack exchange，提问作者driver