春春是一名道路工程师，负责铺设一条长度为 的道路。 铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 块首尾相连的区域，一开始，第 块区域下陷的深度为 。 春春每天可以选择一段连续区间 ，填充这段区间中的每块区域，让其下陷深度减少 。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 。 春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 。 输入 输入文件包含两行，第一行包含一个整数 ，表示道路的长度。 第二行包含 个整数，相邻两数间用一个空格隔开，第 个整数为 。 输出 输出文件仅包含一个整数，即最少需要多少天才能完成任务。 样例输入 复制 6 4 3 2 5 3 5 样例输出 复制 9 提示 【样例解释】 一种可行的最佳方案是，依次选择： 、 、 、 、 、 、 、 、 。 【数据规模与约定】 对于 的数据， ； 对于 的数据， ； 对于 的数据， 。

以下是对该问题的分析与Python代码实现： 问题分析 要让整段道路下陷深度变为0且用时最短，可采用贪心算法。核心思路是比较相邻区域的下陷深度，若后一个区域下陷深度比前一个大，那么多出来的下陷深度就需要额外的天数来填平；若后一个区域下陷深度小于等于前一个，就不需要额外天数。 代码实现 ```python # 读取输入 n = int(input()) # 读取每块区域的下陷深度 depths = list(map(int, input().split())) # 初始化天数为第一块区域的下陷深度 days = depths[0] # 遍历每块区域，从第二块开始 for i in range(1, n): # 如果当前区域下陷深度比前一个区域大 if depths[i] > depths[i - 1]: # 增加额外的天数 days += depths[i] - depths[i - 1] # 输出最少需要的天数 print(days) ``` 代码解释 1. 读取输入：首先读取道路的长度`n`，接着读取每块区域的下陷深度并存储在列表`depths`中。 2. 初始化天数：将天数初始化为第一块区域的下陷深度，因为第一块区域的下陷深度肯定需要相应天数来填平。 3. 遍历区域：从第二块区域开始遍历，比较当前区域和前一个区域的下陷深度。若当前区域下陷深度比前一个大，就把多出来的下陷深度对应的天数累加到总天数中。 4. 输出结果：最后输出最少需要的天数。 复杂度分析 - 时间复杂度：$O(n)$，这里的`n`是道路的长度，因为只需要遍历一次所有区域。 - 空间复杂度：$O(n)$，主要用于存储每块区域的下陷深度。 [2025-12-12 18:28:13 | AI问答 | 428点数解答]