华为OD机试B卷机房布局解析（Python解题指南及详细思路）

题目描述

小明正在规划一个大型数据中心机房，为了使得机柜上的机器都能正常满负荷工作，需要确保在每个机柜边上至少要有一个电箱。
为了简化题目，假设这个机房是一整排，M表示机柜，I表示间隔，请你返回这整排机柜，至少需要多少个电箱。 如果无解请返回 -1 。

输入描述
cabinets = “MIIM”
其中 M 表示机柜，I 表示间隔

输出描述
2
表示至少需要2个电箱
备注 1 ≤ strlen(cabinets) ≤ 10000 其中 cabinets[i] = ‘M’ 或者 ‘I’

用例

数据中心机房电箱规划问题：简单贪心解法

核心解题思路

作为初学者，我们可能第一反应是暴力枚举所有可能放電箱的位置，但那样时间复杂度太高（O(2^n)），不适合长字符串。贪心算法是更好的选择：从左到右扫描字符串，每次遇到一个机柜（'M'）时，优先尝试用右边的间隔（'I'）来覆盖它，如果不行再用左边，否则就判定无解。

为什么贪心有效？

算法步骤：

1. 初始化：计数器 count 记录电箱数，数组 placed 记录每个位置是否已放电箱（避免重复放置）。
2. 扫描字符串：对每个字符：
3. 如果是 'I'，跳过（我们只在遇到 'M' 时行动）。
4. 如果是 'M'：
5. 检查是否已被覆盖（左边或右边已有电箱）。
6. 如果未被覆盖：
7. 优先尝试在右边放電箱（如果右边是 'I'）。
8. 如果右边不行，尝试在左边放電箱（如果左边是 'I'）。
9. 如果都不行，返回 -1。
10. 返回结果：count 就是最少电箱数。

这个算法时间复杂度 O(n)，只扫描一次字符串，非常高效。

代码实现

# 输入部分：读取字符串
cabinets = input().strip()

# 主体函数：计算最少电箱数
def min_electric_boxes(cabinets):
    n = len(cabinets)
    # 如果没有机柜，返回0
    if 'M' not in cabinets:
        return 0
    
    # 初始化：count记录电箱数，placed记录位置是否已放电箱
    count = 0
    placed = [False] * n  # placed[i]为True表示在i位置放电箱
    
    # 遍历每个字符
    for i in range(n):
        if cabinets[i] == 'M':  # 遇到机柜
            covered = False
            # 检查是否已被覆盖：左边或右边已有电箱
            if i - 1 >= 0 and cabinets[i-1] == 'I' and placed[i-1]:
                covered = True  # 左边有电箱覆盖
            if not covered and i + 1 < n and cabinets[i+1] == 'I' and placed[i+1]:
                covered = True  # 右边有电箱覆盖
            
            if not covered:  # 如果未被覆盖，尝试覆盖
                # 优先用右边间隔放电箱
                if i + 1 < n and cabinets[i+1] == 'I':
                    placed[i+1] = True  # 放电箱
                    count += 1
                # 右边不行，用左边间隔放电箱
                elif i - 1 >= 0 and cabinets[i-1] == 'I':
                    placed[i-1] = True  # 放电箱
                    count += 1
                else:  # 左右都不行，无解
                    return -1
    return count

# 输出部分：调用函数并打印
result = min_electric_boxes(cabinets)
print(result)

代码详解

示例测试

用题目例子验证：

总结

这道题教会我们，贪心算法在覆盖类问题中非常实用：从左到右扫描，及时覆盖每个机柜，优先共享电箱。关键点：

作为初学者，多从简单例子入手，理解贪心策略的“局部最优导致全局最优”思想。希望这篇博客帮你掌握这道题！如果有疑问，欢迎留言讨论。

作者：蜗牛的旷野