铺设道路

题目描述

道路长度为 $n$ ，第 $i$ 段下陷深度为 $d_i$ 。每次操作选一段区间 $[L,R]$ （操作前区间内深度均大于 $0$ ），把 $d_L,\dots,d_R$ 同时减 $1$ ，求把整条路填平所需的最少操作次数。输入：第一行 $n$ ，第二行 $d_1,\dots,d_n$ ；输出：最少操作次数。样例输入：n=6，d=[4,3,2,5,3,5]；样例输出：9。数据范围： $1 \le n \le 10^5$ ， $0 \le d_i \le 10^4$ 。

思路

把每次操作看成砖块图（位置为列、高度为 $d_i$ ）里的一条横条：只有比左邻高出来的层，左邻没有砖可铺，必须以该位置为左端点新开一次操作，因此答案是相邻深度差的正部之和 $\sum_{i=1}^{n} \max(d_i - d_{i-1}, 0)$ （约定 $d_0 = 0$ ）。一次线性扫描即可，样例即 $4+3+2=9$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 13:43
# update_at: 2026-10-02 13:43

import sys
from itertools import pairwise


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    depth = [next(data) for _ in range(n)]

    # 每天只能在"深度非零"的连续段内整体 -1，把每个位置填到 0 的次数里
    # 与左邻共用的部分不会重复计数；答案 = 相邻差分的正部之和。
    ans = sum(max(cur - prev, 0) for prev, cur in pairwise([0] + depth))

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:14
 * update_at: 2026-10-06 16:14
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 1e5 + 5;

int n;
ll d[MAXN]; // d[i] 表示第 i 天的道路深度

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &d[i]);

    // 每次操作填平一个区间，把"竖直视角"看成铺横条：
    // 只有比左邻高出来的层必须以 i 为左端点新开一次操作，
    // 答案 = sum(max(d[i] - d[i-1], 0))，约定 d[0] = 0。
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        if (d[i] > d[i - 1])
            ans += d[i] - d[i - 1];

    printf("%lld\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码