题面解释:

为了最小化检查数据中心服务器的时间，我们可以采取以下策略：首先，使用行检查，能够同时检查多行服务器，耗时1秒；然后，使用列检查，单列检查耗时2秒。我们需要读取机架数量及每个机架的服务器数量，并找出最大的服务器数量来决定检查方式。优先进行行检查，尽可能多地覆盖服务器，再用列检查完成剩余的检查。代码实现通过标记已检查的行和计算总耗时来得到最终结果。通过这种方式，我们可以高效地确保所有服务器都得到检查，达到最小的时间消耗。

思路:贪心+递归

对一个数组arr，对min(arr)进行一个行操作。剩下的区间递归进行。直到l = r , 进行列操作 具体细节看代码注释

题解

本题旨在计算对一组服务器高度数组进行检查所需的最小代价。代价的计算方式分为两部分：行操作和列操作。具体来说，我们将根据数组中的最小值执行行操作，并在处理完所有行之后，对单个服务器进行列操作。

1. 行操作: 如果区间内有多个服务器的高度大于当前最小值，我们将这些服务器的高度减少到最小值，这一过程的代价为1秒。此时，我们会递归地处理剩余的区间。

2. 列操作: 当区间缩小至仅包含一个服务器时，必须进行列操作，此时的代价为2秒。

通过这样的递归操作，我们可以有效地计算出整个数组的最小检查代价。算法的核心在于寻找当前区间的最小值，并在此基础上递归处理，直至每个服务器都被检查完毕。

代码分析

• 输入部分: 首先读取服务器数量和高度。
• 递归函数 minCost:
  • 基本条件: 处理了左边界大于右边界和只包含一个元素的特殊情况。
  • 最小值计算: 遍历当前区间以找到最小的服务器高度。
  • 行操作: 使用循环遍历区间，处理所有大于最小值的服务器，进行递归调用。
• 输出部分: 打印计算得到的最小代价。

代码

java

import java.util.Scanner;

public class Main {

    static int[] h;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        h = new int[n + 1];  // 1-based indexing
        for (int i = 1; i <= n; i++) {
            h[i] = sc.nextInt();
        }
        // 计算并输出最小操作代价
        System.out.println(minCost(1, n));
    }

    // 计算区间 [l, r] 的最小代价
    static int minCost(int l, int r) {
        if (l > r) {
            return 0;
        }
        if (l == r) {
            return 2; // 单个服务器默认为单列操作
        }

        int minH = Integer.MAX_VALUE;
        for (int i = l; i <= r; i++) {
            minH = Math.min(minH, h[i]);
        }

        // 行操作
        int cost1 = 1;
        int i = l;
        while (i <= r) {
            if (h[i] > minH) {
                int start = i;
                while (i <= r && h[i] > minH) {
                    i++;
                }
                cost1 += minCost(start, i - 1);
            } else {
                i++;
            }
        }
        return cost1;
    }
}

python

import sys
# 递归深度设置为1000000
sys.setrecursionlimit(1000000)

n_and_rest = sys.stdin.read().split()
n = int(n_and_rest[0])
h = list(map(int, n_and_rest[1:n+1]))
h = [0] + h  # 1-based indexing

def min_cost(l, r):
    if l > r:
        # 空区间的操作代价为0
        return 0
    if l == r:
        # 一个服务器的操作默认为单列操作
        return 2 
    min_h = min(h[l:r+1])
    # 操作1: 用行操作，找到<不是最小高度>的连续区间
    cost1 = 1
    i = l
    while i <= r:
        # 找到连续区间
        if h[i] > min_h:
            # 找到连续区间的起始位置
            start = i
            # 找到连续区间的终止位置
            while i <= r and h[i] > min_h:
                i += 1
            # 递归计算连续区间的最小代价
            cost1 += min_cost(start, i - 1)
        else:
            i += 1
    return cost1

total_min_cost = min_cost(1, n)
print(total_min_cost)

cpp

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

vector<int> h;  // 服务器高度数组

// 计算区间 [l, r] 的最小代价
int minCost(int l, int r) {
    // 如果左边界大于右边界，返回0（无操作）
    if (l > r) {
        return 0;
    }
    
    // 如果区间只包含一个服务器，返回列操作的代价2
    if (l == r) {
        return 2;  
    }

    // 找到当前区间的最小高度
    int minH = INT_MAX;  
    for (int i = l; i <= r; i++) {
        minH = min(minH, h[i]);  // 更新当前最小高度
    }

    // 进行行操作，初始代价为1秒
    int cost1 = 1;  
    int i = l;  // 从左边界开始遍历
    while (i <= r) {
        // 如果当前服务器的高度大于最小值
        if (h[i] > minH) {
            int start = i;  // 记录当前区间的起始位置
            // 向右移动，直到找到不再大于最小值的服务器
            while (i <= r && h[i] > minH) {
                i++;
            }
            // 对于当前找到的区间，递归计算其代价
            cost1 += minCost(start, i - 1);
        } else {
            // 如果当前服务器高度不大于最小值，继续向右移动
            i++;
        }
    }

    return cost1;  // 返回当前区间的总代价
}

int main() {
    int n;
    cin >> n;  // 输入服务器数量
    h.resize(n + 1);  // 调整数组大小以便使用1-based索引
    for (int i = 1; i <= n; i++) {
        cin >> h[i];  // 输入每个服务器的高度
    }

    cout << minCost(1, n) << endl;  // 输出从1到n的最小检查代价
    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

在一个未来的超级数据中心，有一排存放服务器的阵列，阵列由一列一列的机架组成，机架的每一行可以存放一个服务器，每列架子的服务器都是自底向上依次摆放，摆放的个数是随机且大于0的。现在有一个运维机器人用来检查服务器健康状态，机器人有行列2种检查模式：

1. 行检查支持多行服务器一起检查，检查时间为1秒。
2. 列检查仅支持单列服务器检查，检查时间为2秒。

约束说明：

• 允许在同一个服务器检查多次，但同一次行、列检查模式的服务器必须为连续的一段。
• 单独的一个服务器检查，默认采用列检查方式，检查时间为2秒。
• 行、列检查时间跟检查列的服务器数量无关，仅与检查模式相关。

请问机器人最少要花费多少时间才能检查完整个数据中心的服务器。

输入描述

入参分为两行输入:

• 第一行为机架的数量$n$。
• 第二行$n$个整数$rack_1,..., rack_n$空格隔开表示每个机架摆放服务器的数量。

输出描述

检查完所有服务器最少需要的花费时间

样例1

输入

3
5 5 5

输出

1 

说明

采用行检查，因为多行可以一起检查，所以$1$次行扫描就检查完了，耗时$1s$

样例2

输入

5
2 2 1 2 1

输出

4

说明

第一次采用行检查，覆盖$1$~$5$列的第1行服务器，耗时$1s$，第二次采用行检查，覆盖$1$~$2$列的第$2$行服务器，耗时$1s$，第三次采用列检查，覆盖第$4$列第$2$行的服务器，耗时$2s$，总计耗时$4s$

样例3

输入

5
7 4 3 3 5

输出

6

说明

第一次采用行检查，覆盖$1$~$5$列的$1$~$3$行服务器，耗时$1s$，第二次采用行检查，覆盖$1$~$2$列的第$4$行服务器，耗时$1s$，第三次采用列检查，覆盖第$1$列的$5$~$7$行的服务器，耗时$2s$，第四次采用列检查，覆盖第$5$列的$4$~$5$行的服务器，耗时$2s$，总计耗时$6s$