题面解释:

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

思路:贪心+递归

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

题目内容

在一个未来的超级数据中心，有一排存放服务器的阵列，阵列由一列一列的机架组成，机架的每一行可以存放一个服务器，每列架子的服务器都是自底向上依次摆放，摆放的个数是随机且大于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$

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写