[NOIP 2018 提高组] 铺设道路

题意

有 n 段连续道路，第 i 段下陷深度为 d_i。每天可以选择一个连续区间，让区间内所有仍大于 0 的深度都减少 1。问最少多少天能把所有深度变成 0。

思路

把操作反过来看：从全 0 的道路开始，每天选择一个连续区间，让区间内高度增加 1，最后要构造出数组 d。

从左到右看：

第一个位置需要从 0 增到 d[0]，至少要新开 d[0] 层区间；
如果 d[i] <= d[i-1]，前面已经开的区间层数足够覆盖当前位置，不需要新开；
如果 d[i] > d[i-1]，多出来的 d[i]-d[i-1] 层必须从当前位置新开区间。

因此答案就是：

text

1d[0] + sum(max(0, d[i] - d[i-1]))

样例 4 3 2 5 3 5 的计算过程：

位置	深度	相比左侧新增层数	累计答案
1	4	4	4
2	3	0	4
3	2	0	4
4	5	3	7
5	3	0	7
6	5	2	9

Python 知识

整数数组用 sys.stdin.buffer.read() 一次读取，适合 n 到 100000 的数据。
访问相邻元素时，用 for i in range(1, n) 和 depth[i-1] 最直接。
只在出现正向增量时累加，避免把下降部分误算成需要新开操作。

这题的关键是公式化的线性扫描，不额外创建 brute.py。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    depth = data[1:1 + n]

    answer = depth[0]
    for i in range(1, n):
        if depth[i] > depth[i - 1]:
            answer += depth[i] - depth[i - 1]

    print(answer)


if __name__ == "__main__":
    main()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P5019 [NOIP 2018 提高组] 铺设道路 */
/* 从左到右扫描，答案等于所有正向深度增量之和。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
int d[MAXN]; // 每个位置的深度

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
    }

    long long ans = d[1]; // 第一个位置需要新开 d[1] 层
    // 如果当前位置比前一个深，多出的深度必须从当前位置新开操作
    for (int i = 2; i <= n; i++) {
        if (d[i] > d[i - 1]) {
            ans += d[i] - d[i - 1];
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

只扫描一遍数组，时间复杂度是 $O(n)$ 。

空间复杂度是 $O(n)$ ，主要来自输入数组。

总结

这题不要模拟每天填哪段区间。看相邻深度的正向增量：每次比左边更高的部分，都是必须从当前位置新开的层数。

[NOIP 2018 提高组] 铺设道路

目录

题意

思路

Python 知识

代码

复杂度

总结