积木大赛题解

问题分析

本题要求计算搭建一座宽度为$n$的大厦所需的最少操作次数。每块积木的最终高度为$h_i$，每次操作可以选择一段连续区间$[L, R]$，将区间内所有积木的高度增加$1$。初始时所有积木高度均为$0$。

算法思路

本题可采用贪心算法求解，核心思路是通过分析相邻积木的高度差来计算最少操作次数：

1. 当从左到右依次处理每块积木时，若当前积木高度$h[i]$大于前一块积木高度$h[i-1]$，说明需要额外进行$(h[i] - h[i-1])$次操作。这是因为前一块积木的高度限制了可延伸过来的操作次数，差值部分必须通过新的操作来补充。
2. 若当前积木高度小于或等于前一块积木高度，则不需要额外操作，因为在处理前一块积木时的操作可以自然延伸到当前位置。

算法实现

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>

const int N = 1e5 + 10;
int h[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    
    int ans = 0;
    // 初始时h[0]视为0（前一块积木高度）
    for (int i = 1; i <= n; i++)
        if (h[i - 1] < h[i])
            ans += h[i] - h[i - 1];
    
    cout << ans;
    return 0;
}

代码解析

1. 初始化：读取大厦宽度$n$和每块积木的目标高度$h[i]$（$1 \leq i \leq n$）。
2. 遍历计算：从第一块积木开始遍历，将当前积木高度$h[i]$与前一块积木高度$h[i-1]$（初始时$h[0] = 0$）比较：
   • 若$h[i] > h[i-1]$，则累加高度差$(h[i] - h[i-1])$到答案中，这部分是需要额外进行的操作。
   • 若$h[i] \leq h[i-1]$，则不需要额外操作。
3. 输出结果：累加得到的结果即为最少操作次数。

样例分析

以样例输入为例：

• 输入：$n=5$，$h=[2,3,4,1,2]$
• 计算过程：
  • $i=1$：$h[1]=2$，$h[0]=0$，差值为$2$， ans=$2$
  • $i=2$：$h[2]=3$，$h[1]=2$，差值为$1$， ans=$3$
  • $i=3$：$h[3]=4$，$h[2]=3$，差值为$1$， ans=$4$
  • $i=4$：$h[4]=1$，$h[3]=4$，无差值， ans保持$4$
  • $i=5$：$h[5]=2$，$h[4]=1$，差值为$1$， ans=$5$
• 输出结果为$5$，与样例一致。

复杂度分析

• 时间复杂度：$O(n)$，仅需遍历一次积木高度数组。
• 空间复杂度：$O(n)$，需要存储$n$块积木的高度。

算法标签

• 贪心算法
• 前缀差分析
• 线性遍历

数据范围

• 对于$30\%$的数据，$1 \leq n \leq 10$
• 对于$60\%$的数据，$1 \leq n \leq 1000$
• 对于$100\%$的数据，$1 \leq n \leq 100000$，$0 \leq h_i \leq 10000$