最少操作次数等于高度数组相邻差分中的所有正增量之和。
OJ: luogu
题目 ID: P1969
难度:普及/提高-
标签:贪心差分思维noip
日期: 2026-06-19 02:12
题意
有 n 列积木，开始时所有列高度都是 0。
一次操作可以选一个连续区间 [l, r]，让这个区间内所有列的高度都同时增加 1。
目标是最终得到高度数组 h[1..n]，要求最少操作次数。
思路
先看最直接的想法：把整个建造过程按“层”来模拟。
每次扫描当前高度数组，把所有正高度的连续段各减去 1，这就等价于在这一层对每个连续段各做一次区间加法：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：小数据暴力解。
// 一层一层地削去所有正高度连续段，每削一层连续段就对应一次操作。
const int MAXN = 100000 + 5;
int n;
int h[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
long long ans = 0;
while (true) {
bool has_positive = false;
int i = 1;
while (i <= n) {
while (i <= n && h[i] == 0) {
i++;
}
if (i > n) {
break;
}
has_positive = true;
ans++;
while (i <= n && h[i] > 0) {
h[i]--;
i++;
}
}
if (!has_positive) {
break;
}
}
cout << ans << '\n';
return 0;
}这个写法很好理解，但如果高度很大，就要一层一层地削，效率不够高。
真正的关键在于：我们只需要统计“新的操作从哪里开始”。
从左到右看高度数组：
- 第
1列想从0长到h[1]，显然至少要新开h[1]次操作； - 对于第
i列：- 如果
h[i] <= h[i-1]，那么前一列已经开过的那些操作，完全可以覆盖到这里，不需要新开； - 如果
h[i] > h[i-1]，那么多出来的这h[i] - h[i-1]层，左边没有办法替它补上，只能从第i列这里重新开始新操作。
- 如果
所以答案就是：
h[1] + sum(max(0, h[i] - h[i-1]))
也可以把 h[0] 看成 0，统一写成：
sum(max(0, h[i] - h[i-1]))
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int n;
long long h[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
long long ans = 0;
long long prev = 0; // h[0] 视为 0，统一处理第一列
for (int i = 1; i <= n; i++) {
if (h[i] > prev) {
ans += h[i] - prev;
}
prev = h[i];
}
cout << ans << '\n';
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题表面是区间操作，实际上只需要看相邻两列高度的“正增长”。
哪里比左边高，哪里就必须新开操作；把所有这种正增量加起来，就是最优答案。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
