从积木题看算法思维：游程编码与连续段统计在信奥竞赛中的应用

1. 项目概述：从一道赛题看算法思维的构建

最近在带学生备赛，翻看往年真题时，常州市赛2023年的这道B4222积木题让我眼前一亮。它不像一些复杂的图论或动态规划题那样一上来就让人发怵，而是用一个非常生活化的“搭积木”场景，包裹了一个经典的算法问题。题目大意是给定一组不同高度的积木，要求计算在只能看到“轮廓”的前提下，最少需要多少块积木才能拼出这个轮廓。这听起来是不是有点像我们小时候玩的游戏？但恰恰是这种从具象到抽象的转化，最能考察一个选手的基本功：对数据的理解、对问题本质的挖掘，以及将现实模型转化为可计算步骤的能力。

很多刚接触信奥（信息学奥林匹克）的同学，一看到“市赛”、“算法”这些词可能就觉得高深莫测，下意识地去想有没有什么“高级”的模板可以套用。其实不然。这道题的核心，本质上是对一个整数序列进行一种特定的“压缩”或“简化”操作。它适合所有已经掌握C++基础语法（数组、循环、条件判断）、正开始接触基础算法的同学来练习。通过解决它，你不仅能巩固编程基础，更能学习到一种至关重要的思维方法：如何忽略无关细节，抓住影响结果的关键变量。接下来，我就结合这道B4222，详细拆解一下从读题到AC（Accepted，通过）的完整思考与实现过程，其中会穿插很多我在教学和解题中总结的“避坑”经验。

2. 核心需求解析与问题抽象

2.1 题目场景还原与关键信息提取

我们先抛开代码，像侦探一样仔细审视题目描述（这里我根据常见赛题风格进行还原和阐述）。假设我们面前有一排立在地上的积木柱子，每根柱子由若干块单位高度的积木方块叠成，因此柱子的高度就是一个正整数。现在我们从侧面远远望去，只能看到它们的“天际线”或者说“轮廓”。如果几根相邻的柱子高度相同，那么在轮廓上它们就会连成一条水平的线段，我们无法分辨中间到底有多少根柱子。题目要我们求的是，能形成这个轮廓的、最少需要的积木柱子数量。

举个例子，假设原始高度序列是[2, 3, 3, 2]。它的轮廓是：先是一个2，然后升到3并保持水平一段，再降回2。为了用最少的柱子实现这个轮廓，我们只需要三根柱子：高度分别为2， 3， 2。因为中间两个高度为3的柱子，在轮廓上合并了。所以答案就是3。

关键信息点提炼：

1. 输入：一个整数序列，代表一排积木柱的初始高度。
2. 操作：寻找轮廓。轮廓变化的点只发生在高度发生变化的位置。
3. 输出：构成这个轮廓所需的最少积木柱数量。
4. 核心逻辑：相邻且高度相同的柱子，在轮廓视角下可以“合并”视为一根。

注意：这里最容易产生的误解是去考虑“积木方块”的总数。题目问的是“柱子”的数量，而不是“方块”的数量。这是一个典型的计数对象转换，务必在审题时圈出来。

2.2 问题抽象与算法思路确立

将上述自然语言描述抽象成算法问题，是解题的关键一步。

抽象过程： 我们有一个数组heights[]。我们需要遍历这个数组，但目的不是处理每一个元素，而是找出所有“连续相同高度子序列”的个数。每一个这样的子序列，在最终的最少柱子表示中，都只贡献一根柱子。

思路确立： 因此，算法变得非常直接：

1. 如果数组为空，显然不需要柱子，答案为0。
2. 初始化计数器count = 1。为什么是1？因为至少第一根柱子总是需要的，它开启了一个新的“连续段”。
3. 从第二根柱子开始，依次和它前面的那根柱子比较高度。
   • 如果当前高度heights[i]和前一高度heights[i-1]不同，说明轮廓在这里发生了变化，我们需要一根新的柱子来体现这个变化，所以count++。
   • 如果相同，说明当前柱子还在上一个“连续段”中，轮廓没有变化，我们不需要为它新增柱子计数。
4. 遍历结束后，count的值就是所需的最少柱子数。

这个思路的时间复杂度是 O(N)，只需要一次线性扫描，空间复杂度是 O(1)，仅需几个变量，对于信奥竞赛的限制条件来说绰绰有余。

为什么这样想？—— 思维层面的剖析这实际上运用了“游程编码”（Run-Length Encoding, RLE）的思想。我们不是存储每一个具体值，而是存储“值的变化点”。在本题中，“值”就是高度，“变化点”就是高度发生改变的位置。计数器的每一次增加，都对应轮廓上的一个转折点（包括起点）。这种“关注变化，忽略重复”的思维，在数据处理、信号处理乃至游戏开发中都非常常见。

3. 代码实现与逐行精讲

有了清晰的思路，我们用C++来实现。这里我会提供两个版本的代码：一个是最直观的版本，另一个是稍作简化的版本，并解释其中的每一个细节。

3.1 版本一：清晰直观版

#include <iostream> #include <vector> using namespace std; int main() { int n; // 积木柱的数量 cin >> n; // 边界情况处理：如果没有积木柱，直接输出0并结束 if (n == 0) { cout << 0 << endl; return 0; } vector<int> heights(n); // 使用动态数组vector存储高度，避免固定数组可能的内存浪费 for (int i = 0; i < n; ++i) { cin >> heights[i]; // 读入所有高度 } int min_blocks = 1; // 最少柱子数，初始化为1，因为第一根柱子总是独立的 // 从第二根柱子开始遍历（下标1） for (int i = 1; i < n; ++i) { // 核心判断：当前柱子高度是否与前一根不同？ if (heights[i] != heights[i - 1]) { min_blocks++; // 如果不同，则需要一根新柱子来体现轮廓变化 } // 如果相同，则什么都不做，继续循环 } cout << min_blocks << endl; // 输出结果 return 0; }

逐行精讲与避坑指南：

1. #include <vector>：虽然题目可能给出了n的范围，使用普通数组int heights[100005]也可以，但我更推荐使用vector。它是一种动态数组，更现代、更安全（避免栈溢出），也更能体现C++标准库的运用。这是从“C风格”向“C++风格”过渡的好习惯。
2. 边界处理if (n == 0)：这是一个非常重要的编程习惯。即使题目可能保证n>=1，主动处理边界情况能使你的程序更健壮，逻辑更完整。在竞赛中，这能避免因未预料到的边界数据导致的运行时错误（RE）。
3. min_blocks初始化为1：这是思路的直接体现。只要有一根柱子，它就算一个“连续段”。很多同学在这里会初始化为0，然后在循环里从第一根开始判断，这样容易在空数组或单元素数组时出错。初始化为1并让循环从i=1开始，逻辑更清晰。
4. 循环条件for (int i = 1; i < n; ++i)：注意是i < n，确保不会访问heights[n]（越界）。使用前置自增++i是个人习惯，对于内置类型它与i++效率无异，但养成好习惯有益无害。
5. 核心判断if (heights[i] != heights[i - 1])：这是算法的灵魂。比较的是当前元素和它的前一个元素。一定要想清楚下标，新手常犯的错误是比较heights[i]和heights[i+1]，这会导致最后一次循环越界。
6. 输出与返回：记得输出换行endl，这符合评测机的通常预期。return 0表示程序正常结束。

3.2 版本二：紧凑输入版

这个版本在输入的同时进行判断，节省了一个存储所有高度的数组空间。当n很大时，这能节省可观的内存，但逻辑上稍微绕一点。

#include <iostream> using namespace std; int main() { int n; cin >> n; if (n == 0) { cout << 0 << endl; return 0; } int prev_height, current_height; cin >> prev_height; // 先读入第一根柱子的高度 int min_blocks = 1; for (int i = 1; i < n; ++i) { cin >> current_height; // 读入当前柱子的高度 if (current_height != prev_height) { min_blocks++; } prev_height = current_height; // 关键：将“当前”变为下一轮的“之前” } cout << min_blocks << endl; return 0; }

这个版本的技巧与易错点：

• 双变量滚动：我们只维护两个变量prev_height和current_height，分别代表“前一个高度”和“当前高度”。
• 状态更新：在每次判断后，必须执行prev_height = current_height;。这是整个逻辑正确运行的关键，它保证了在下一轮循环中，prev_height始终是current_height的前一个值。忘记这一步是常见错误，会导致比较对象错乱。
• 适用场景：当问题只需要顺序处理数据，且不需要回头访问之前的数据时，这种“流式处理”方法非常高效。它不仅省空间，有时还能省时间（减少内存访问）。这道题完美符合条件。

实操心得：对于初学者，我建议先从版本一开始写，逻辑清晰不易错。当你对问题理解非常透彻后，可以尝试版本二，这是一种重要的空间优化技巧。在竞赛中，根据数据范围（本题n一般不会太大）选择即可。版本一更具普适性和可读性。

4. 测试用例设计与调试思维

写完代码不等于完事，设计测试用例验证程序的正确性是必备技能。下面我设计几组有针对性的测试数据，并说明它们覆盖了哪些边界和特殊情况。

如何测试？

1. 本地测试：你可以将上面的输入数据保存为in.txt，在命令行运行你的程序，并将输出重定向到文件，再与预期输出对比。

   # 假设编译后的程序叫`blocks.exe` blocks.exe < in.txt > out.txt

   然后查看out.txt的内容。
2. 在线评测机（OJ）思维：在OJ上提交后，如果出错，它会返回一个错误类型（如WA, RE）。这时，你需要根据错误类型和上述测试用例来“脑补”可能出错的数据。
   • WA (Wrong Answer)：结果不对。重点检查算法逻辑，尤其是循环的起始、结束条件和比较语句。用“全部相同”和“单元素”用例最容易发现初始值错误。
   • RE (Runtime Error)：运行时错误。最常见的是数组越界。检查你的数组大小是否足够（如果用静态数组），或者vector访问下标是否在[0, n-1]范围内。n=0时的处理不当也可能导致RE。
   • TLE (Time Limit Exceeded)：超时。本题算法是O(N)，几乎不可能超时。如果发生，检查是否有死循环（比如循环变量更新错误）。

调试技巧：在代码关键位置（如循环开始、判断分支）插入临时输出语句，打印变量值，是理解程序运行过程、定位bug的最朴实有效的方法。

5. 算法扩展与思维提升

这道题虽然简单，但它背后的思想可以延伸到更复杂的问题。理解这一点，你的算法思维就能再上一个台阶。

5.1 问题变体思考

如果题目不是求最少柱子数，而是求轮廓线本身的长度（假设柱子宽度为1）呢？

• 分析：轮廓线长度由水平部分和垂直部分构成。水平部分就是每个“连续段”的长度（柱子数），垂直部分就是高度差。但仔细想想，最少柱子数其实等于轮廓线中“转折点”的数量。而求轮廓线总长度，则需要计算所有相邻不同高度之间的“台阶”高度差之和，再加上起始和结束的宽度？不，这需要更严谨的定义。实际上，一个更经典的“天际线”问题是给定一系列矩形（积木柱），求它们轮廓的顶点序列。这就引出了著名的“天际线问题”（Skyline Problem），通常需要用扫描线算法和优先队列来解决，复杂度也更高。通过对比，你能深刻体会到本题的简化之美——它只关心计数，不关心具体几何形状。

5.2 同类问题举一反三

掌握“统计连续段”或“检测变化点”这个模式，你可以解决很多类似问题：

1. 字符串压缩：例如，将“aaabbcccc”压缩成“a3b2c4”。这同样是游程编码，遍历字符串，计数连续相同字符。
2. 计算分组数：有一组学生按身高排序后，需要分成若干组，要求同组内身高差不超过某个值。这需要在遍历时，不仅比较相邻项是否“相等”，还要判断是否“满足某个条件”，从而决定是否开启新的一组。
3. 信号平滑与边缘检测：在数据处理中，连续相同的值可以视为平稳信号，而值的变化点可能就是需要关注的“边缘”或“事件”。

思维模式总结：遇到需要对序列进行“分段”或“合并相邻同类项”的问题时，第一时间想到这种单次扫描、比较相邻元素的模板。它的核心框架是：

int count = 1; // 或0，取决于第一段如何定义 for (int i = 1; i < n; i++) { if (data[i] != data[i-1]) { // 这里的“!=”可以替换成任何分段条件 count++; // 可选：在这里记录分段点信息 } }

6. 竞赛实战中的注意事项与效率提升

在信奥竞赛的实战环境中，除了写出正确的算法，还有一些细节能决定成败。

6.1 输入输出效率

对于本题，数据量不会太大，使用标准的cin/cout完全足够。但如果遇到输入数据量极大（如n > 10^5）的题目，就需要考虑输入输出效率。

• 关闭流同步：在main函数开头加入以下两行，可以大幅提升cin/cout的速度，使其接近scanf/printf。

  ios::sync_with_stdio(false); cin.tie(nullptr);

  注意：一旦使用了这两行，就不能再混用cin/cout和scanf/printf，否则可能导致输入输出顺序错乱。

• 使用scanf/printf：C风格的输入输出在默认情况下比未优化的cin/cout快。对于纯整数或浮点数读取，scanf也很方便。
• 使用快读函数：对于极端情况（n > 10^6），可以手写一个读取整数的函数，通过逐字符读取来获得最高速度。这是竞赛中的高级技巧。

对于本题的建议：直接使用cin/cout，保持代码简洁清晰。在时间限制宽松的赛题中，可读性比那一点点微乎其微的效率提升更重要。

6.2 代码风格与可读性

清晰的代码风格能让你在调试时更快地找到问题，也方便他人（或未来的你）阅读。

• 变量命名：使用有意义的名称，如min_blocks,heights，而不是a,b,ans。
• 适当注释：在关键逻辑处（如算法核心、边界处理）写上简短注释。
• 合理缩进与空格：让代码结构一目了然。大多数现代编辑器（如VSCode）都有自动格式化功能（Shift+Alt+F）。

6.3 心理与时间策略

• 先保证正确，再追求优化：像本题，先写出O(N)时间、O(N)空间（版本一）的正确代码。提交通过后，如果时间充裕，再考虑能否优化成O(1)空间（版本二）。切忌一开始就追求“完美”而写出复杂易错的代码。
• 善用样例：题目给出的样例输入输出是第一个测试工具。确保你的程序能通过样例。
• 自己构造临界数据：思考n=0,n=1,n=最大值，以及所有元素相同、全部递增、全部递减等情况。这能帮你发现大部分边界错误。

这道B4222积木题，就像一块很好的“基础积木”。它本身不复杂，但搭建起了从问题理解、抽象建模、算法设计、代码实现到测试调试的完整流程。解决它的价值不在于算法本身有多高深，而在于完整地实践了一次解题的标准化思考过程。在信奥学习的道路上，把每一道这样的基础题吃透，积累起来的思维模式和代码经验，才是应对未来更复杂挑战的坚实基石。下次当你遇到一个看似新颖的问题时，不妨先问问自己：它是不是某个基本模式的“换装”？能不能像处理这些积木一样，找到那个决定性的“变化点”？