题面描述

小明正在规划一个大型数据中心机房。为了确保机柜上的机器能够正常满负荷工作，必须确保在每个机柜（M）旁边至少有一个电箱（E）。为了简化问题，机房被抽象为一整排，由字符组成的字符串表示，其中：

• 'M' 表示机柜
• 'I' 表示间隔（可以放置电箱的位置）

请编写一个程序，返回这整排机柜至少需要多少个电箱。如果无法满足要求，返回 -1。

思路

为了确保每个机柜（M）旁边至少有一个电箱（E），我们需要在合适的位置放置电箱。由于电箱只能放置在间隔（I）的位置，我们的策略如下：

1. 遍历字符串：从左到右遍历每个字符。
2. 处理机柜：
   • 对于每个 'M'，检查其左侧和右侧是否已经有电箱覆盖。
   • 如果左侧已有电箱覆盖，则无需额外操作。
   • 如果右侧是 'I' 且尚未放置电箱，则在右侧放置电箱。
   • 如果右侧不能放置电箱，但左侧是 'I' 且尚未放置电箱，则在左侧放置电箱。
   • 如果上述两种情况都无法满足，则无法覆盖该机柜，返回 -1。
3. 统计电箱数量：记录放置的电箱数量，确保总数最小化。

这种贪心策略确保每次尽可能覆盖当前机柜，同时不影响后续机柜的覆盖。

cpp

#include <bits/stdc++.h>
using namespace std;

// 函数用于计算最少需要的电箱数量
int minElectricBoxes(string cabinets) {
    int n = cabinets.length();
    // 用于标记每个位置是否有电箱
    vector<bool> hasBox(n, false);
    int count = 0;
    
    for(int i = 0; i < n; ++i){
        if(cabinets[i] == 'M'){
            bool covered = false;
            // 检查左侧是否有电箱
            if(i > 0 && hasBox[i-1]){
                covered = true;
            }
            // 检查右侧是否有电箱
            if(i < n-1 && hasBox[i+1]){
                covered = true;
            }
            if(covered){
                continue;
            }
            // 优先在右侧放置电箱
            if(i < n-1 && cabinets[i+1] == 'I' && !hasBox[i+1]){
                hasBox[i+1] = true;
                count++;
            }
            // 如果右侧不能放置，则尝试在左侧放置电箱
            else if(i > 0 && cabinets[i-1] == 'I' && !hasBox[i-1]){
                hasBox[i-1] = true;
                count++;
            }
            else{
                // 无法放置电箱
                return -1;
            }
        }
    }
    return count;
}

int main(){
    string cabinets;
    cin >> cabinets;
    cout << minElectricBoxes(cabinets) << endl;
}

python

def min_electric_boxes(cabinets: str) -> int:
    n = len(cabinets)
    has_box = [False] * n  # 标记每个位置是否有电箱
    count = 0
    
    for i in range(n):
        if cabinets[i] == 'M':
            covered = False
            # 检查左侧是否有电箱
            if i > 0 and has_box[i-1]:
                covered = True
            # 检查右侧是否有电箱
            if i < n-1 and has_box[i+1]:
                covered = True
            if covered:
                continue
            # 优先在右侧放置电箱
            if i < n-1 and cabinets[i+1] == 'I' and not has_box[i+1]:
                has_box[i+1] = True
                count +=1
            # 如果右侧不能放置，则尝试在左侧放置电箱
            elif i > 0 and cabinets[i-1] == 'I' and not has_box[i-1]:
                has_box[i-1] = True
                count +=1
            else:
                # 无法放置电箱
                return -1
    return count

if __name__ == "__main__":
    cabinets = input().strip()
    print(min_electric_boxes(cabinets))

java

import java.util.*;

public class Main {
    // 函数用于计算最少需要的电箱数量
    public static int minElectricBoxes(String cabinets) {
        int n = cabinets.length();
        boolean[] hasBox = new boolean[n]; // 标记每个位置是否有电箱
        int count = 0;
        
        for(int i = 0; i < n; i++){
            if(cabinets.charAt(i) == 'M'){
                boolean covered = false;
                // 检查左侧是否有电箱
                if(i > 0 && hasBox[i-1]){
                    covered = true;
                }
                // 检查右侧是否有电箱
                if(i < n-1 && hasBox[i+1]){
                    covered = true;
                }
                if(covered){
                    continue;
                }
                // 优先在右侧放置电箱
                if(i < n-1 && cabinets.charAt(i+1) == 'I' && !hasBox[i+1]){
                    hasBox[i+1] = true;
                    count++;
                }
                // 如果右侧不能放置，则尝试在左侧放置电箱
                else if(i > 0 && cabinets.charAt(i-1) == 'I' && !hasBox[i-1]){
                    hasBox[i-1] = true;
                    count++;
                }
                else{
                    // 无法放置电箱
                    return -1;
                }
            }
        }
        return count;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String cabinets = sc.next();
        System.out.println(minElectricBoxes(cabinets));
    }
}

题目描述

小明正在规划一个大型数据中心机房，为了使得机柜上的机器都能正常满负荷工作，需要确保在每个机柜边上至少要有一个电箱。

为了简化题目，假设这个机房是一整排， $M$ 表示机柜， $I$ 表示间隔，请你返回这整排机柜，至少需要多少个电箱。 如果无解请返回 $-1$ 。

输入描述

cabinets = "MIIM"

其中 $M$ 表示机柜， $I$ 表示间隔

输出描述

2

表示至少需要 $2$ 个电箱

备注

$1 ≤ strlen(cabinets) ≤ 10000$ 其中 $cabinets[i]$ = '$M$' 或者 '$I$'

样例1

输入

MIIM

输出

2

样例2

输入

MIM

输出

1

样例3

输入

M

输出

-1

样例4

输入

MMM

输出

-1

样例5

输入

I

输出

0