A21389. 砖块消除问题有一个砖块消消乐游戏，游戏画面由 n 列砖组成，每列都有若干块砖，每块砖都是 1×1 的正方形且砖块之间排列整齐（每块砖的厚度及砖块之间的缝隙忽略不计）。玩家每次可以按照以下要求，选定一个矩形区域，将该矩形区域的所有砖块消除：该矩形区域内每块砖都是完整的，即不能选定某块砖的一部分。例如：可以选择下方左图中的矩形区域（绿色框），不可以选定下方右图中的矩形区域（红色框）。2. 该矩形区域…
填空题
较难
知识点
题目描述
砖块消除问题
有一个砖块消消乐游戏，游戏画面由 n 列砖组成，每列都有若干块砖，每块砖都是 1×1 的正方形且砖块之间排列整齐（每块砖的厚度及砖块之间的缝隙忽略不计）。
玩家每次可以按照以下要求，选定一个矩形区域，将该矩形区域的所有砖块消除：
该矩形区域内每块砖都是完整的，即不能选定某块砖的一部分。例如：可以选择下方左图中的矩形区域（绿色框），不可以选定下方右图中的矩形区域（红色框）。
2. 该矩形区域内不能有空白部分。例如：不可以选定下图中的矩形区域（红色框）。
给定砖的列数 n，以及从左至右每列砖的砖块数量，请计算消除完所有砖块最少需要选定多少次矩形区域。
例如：n = 3；从左至右列砖的砖块数量分别是 2、3、2，将所有砖块全部消除最少需要选定 2 次。
第 1 次，选定绿色框的矩形区域，将 6 块砖消除，剩余 1 块砖；
第 2 次，选定剩余的 1 块砖并消除。
输入描述
1. 第一行输入一个整数 n（1 ≤ n ≤ 1e5），表示有多少列砖；
2. 第二行输入 n 个整数（1 ≤ 整数 ≤ 100），分别表示从左至右每列砖的砖块数量，整数之间以一个空格隔开。
输出描述
输出一个整数，表示消除完所有砖块最少需要选定多少次矩形区域。
样例输入
3
2 3 2样例输出
2参考答案
n = int(input())
h = list(map(int, input().split())) # 存储每列砖块的初始高度
count = 0 # 记录最少消除次数
while True: # 步骤1：检查是否所有砖块都已消除
all_zero = True
min_h = float('inf') # 记录当前非零高度中的最小值
for num in h:
if num > 0:
all_zero = False
if num < min_h:
min_h = num # 更新最小高度
if all_zero:
break
# 所有砖块消除完毕，退出循环
# 步骤2：统计当前非零高度的连续段数量（每段可一次消除）
segments = 0
in_segment = False # 标记是否处于连续段中
for num in h:
if num > 0:
if not in_segment:
# 进入新的连续段，计数+1
segments += 1
in_segment = True
else: # 离开连续段
in_segment = False
count += segments
# 累加本次消除的段数
# 步骤3：将当前所有非零高度减去最小高度（模拟消除这部分砖块
for i in range(n):
if h[i] > 0:
h[i] -= min_h
print(count)
上一题
下一题