A21372. 摧毁积木塔（tower.cpp）
填空题
中等
知识点
题目描述
摧毁积木塔（tower.cpp）
题目描述
圣诞节联欢活动有拆积木塔游戏。n 座积木塔（编号 1~n），第 i 座塔高度为 hᵢ（由 hᵢ个正方体积木组成，长和宽均为 1）。积木块分为：
内部块：上下左右四个方向均有相邻积木块或地面；
边界块：非内部块。每次操作摧毁当前所有边界块，求摧毁所有积木块所需的操作次数。
输入描述
第一行包含整数 n（1≤n≤1e5）；第二行包含 n 个整数 h₁、h₂、…、hₙ（1≤hᵢ≤1e5），表示每座塔的高度。
输出描述
输出所需操作次数。
样例输入1
6
2 1 4 6 2 2
样例输出1
3
样例输入2
7
3 3 3 1 3 3 3
样例输出2
2
样例1解释:
每次边界块都用红色标记。第一次操作后，还剩下四个块，第二次操作后只剩下一个。这最后一个块在第三次操作中被摧毁。
参考答案
#include <bits/stdc++.h>
usingnamespacestd;
constint N = 1e5 + 5; // 数组大小，适配题目数据范围
int h[N]; // 存储每根柱子的初始高度
int f[N]; // f[i]：第i根柱子完全摧毁的最少操作次数
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> h[i];
f[i] = h[i]; // 初始化：最少操作次数不超过自身高度
}
// 第一次遍历：从左到右，考虑左侧柱子的限制
for (int i = 2; i <= n; ++i)
{ // i从2开始（避免i-1=0越界）
f[i] = min(f[i], f[i-1] + 1);
}
// 第二次遍历：从右到左，考虑右侧柱子的限制
for (int i = n-1; i >= 1; --i) // i从n-1开始（避免i+1=n+1越界）
{
f[i] = min(f[i], f[i+1] + 1);
}
// 找所有f[i]的最大值（总操作次数由耗时最久的柱子决定）
int ans = 0;
for (int i = 1; i <= n; ++i)
{
ans = max(ans, f[i]);
}
cout << ans << endl;
return0;
}
上一题
下一题