道路工程师春春：巧用贪心算法最短时间填平下陷道路！

以下是对该问题的分析与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)$，主要用于存储每块区域的下陷深度。 ######[AI问答 | 428点数解答 | 2025-12-12 18:28:13]