[NOIP2013-提高]积木大赛

形式化题目

目标高度序列 $h_1..h_n$ （初始全 0）。每次操作选区间 $[l,r]$ 整体 +1，求搭出目标的最少操作次数。

正解

思路

1. 贪心 / 差分视角

每次操作是一段连续区间 +1，相当于在差分数组上做「 $d_l{+}1,\ d_{r+1}{-}1$ 」。目标差分 $d_i = h_i - h_{i-1}$ （ $h_0=0$ ）：

$d_i > 0$ 的位置必须由「覆盖 $i$ 且不覆盖 $i-1$ 」的操作开启，至少 $d_i$ 次；
$d_i \le 0$ 的位置可以被左边延伸的操作顺带覆盖，不新增次数。

因此最少操作数 = $\sum \max(0,\ h_i - h_{i-1})$ 。一遍扫描即可。

2. 直观理解

从左到右搭：遇到比左边高的部分必须新开操作（爬升段），下降段直接让之前的操作提前结束，不花额外次数。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){ios::sync_with_stdio(false); cin.tie(nullptr); int n; if(!(cin>>n)) return 0; ll prev=0,total=0; for(int i=0;i<n;i++){ll h;cin>>h; if(h>prev) total+=h-prev; prev=h;} cout<<total<<'\n'; return 0;}

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
26
27
28
29
30#!/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 10:42
# update_at: 2026-10-02 10:42

import sys


def min_operations(heights: list[int]) -> int:
    """最少操作数：从 0 起，逐块累加"比左邻高出的部分"，下降段贡献 0。"""
    prev = 0  # 左边没有积木，虚拟高度 0
    total = 0
    for height in heights:
        if height > prev:           # 这段爬升必须由不覆盖左邻的操作补齐
            total += height - prev
        prev = height
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    heights = [next(data) for _ in range(n)]  # 第 i 块的目标高度 h_i
    print(min_operations(heights))


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ （读入数组；可流式 $O(1)$ ）。

总结

「区间 +1 凑目标」= 差分正部求和，经典贪心。
相邻差分的正负分解是所有「区间加减计数」问题的基本功。

[NOIP2013-提高]积木大赛

目录

形式化题目

正解

思路

1. 贪心 / 差分视角

2. 直观理解

代码

复杂度

总结