3090.[NOIP2018 提高组] 铺设道路

算法思路

1. 问题分析

本题本质是贪心算法的应用场景，核心在于将道路填平操作转化为对高度差的处理。通过分析相邻区域的高度关系，发现最优策略的关键规律：每次操作本质是在消除高度差。最终转化为计算相邻区域高度差之和的数学问题。

2. 解决策略

1. 基础操作分析：填平整个道路的最小天数等于所有区域深度之和减去"可并行操作"节省的天数
2. 关键规律发现：当 $d_i ≤ d_{i-1}$ 时，填平 $d_{i-1}$ 的过程中会同时处理 $d_i$
3. 核心计算：
   • 初始化天数为第一个区域的深度 $a_0$
   • 遍历后续区域，若 $a_i>a_{i-1}$，则累加高度差 $(a_i - a_{i-1})$
   • 总天数 = $a_0 + \sum_{i=1}^{n-1} max(a_i - a_{i-1}, 0)$

3. 复杂度分析

• 时间复杂度：$O(n)$
  仅需一次线性扫描数组，每个元素访问一次
• 空间复杂度：$O(n)$
  存储深度数组所需空间，若使用流式读取可优化至 $O(1)$
• 正确性依据：每次高度差累加对应必须单独执行的操作天数

---

代码实现

C++解法

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    // 读取道路长度和深度数组
6    int n;
7    cin >> n;
8    int a[n];
9    for (int i = 0; i < n; i++) {
10        cin >> a[i];
11    }
12
13    long long ans = a[0];  // 初始化天数为第一个区域的深度
14    // 遍历后续区域，累加上升高度差
15    for (int i = 1; i < n; i++) {
16        if (a[i] > a[i - 1]) {
17            ans += a[i] - a[i - 1];  // O(1)操作，累计高度差
18        }
19    }
20    cout << ans;
21    return 0;
22}

代码解释：

1. 输入处理
   • n：道路区域数量（1≤n≤100000）
   • a[]：存储每个区域下陷深度的数组
2. 核心逻辑
   • 初始化 ans = a[0]：第一个区域必须单独操作
   • 高度差累加：当后一区域更深时，差值即为新增操作天数
3. 边界处理
   • 数组索引从0开始，符合C++标准
   • 使用 long long 防整数溢出（极端情况总和>2e9）

Python3解法

python
复制
1def main():
2    import sys
3    data = sys.stdin.read().split()
4    n = int(data[0])  # 道路长度
5    a = list(map(int, data[1:1+n]))  # 区域深度列表
6    
7    ans = a[0]  # 初始化天数为首区域深度
8    # 遍历计算高度差
9    for i in range(1, n):
10        if a[i] > a[i-1]:
11            ans += a[i] - a[i-1]  # 累加上升高度差
12    
13    print(ans)
14
15if __name__ == "__main__":
16    main()

代码解释：

1. 与C++差异
   • 动态列表解析输入，无需预分配空间
   • 索引从0开始，逻辑完全一致
2. Python特性
   • sys.stdin.read() 批量读取提高IO效率
   • 列表切片 data[1:1+n] 精准提取深度数据
3. 关键操作
   • 循环中直接比较相邻元素，避免额外存储
   • 自动处理大整数，无需类型声明

---

复杂度对比

选择建议：

• 竞赛场景：优先选用C++，尤其$n>10^5$时效率优势显著
• 原型验证：选用Python简化逻辑验证和边界测试
• 内存敏感：两者皆可通过流式读取优化至$O(1)$空间