1. 项目概述从“过山车”到算法思维的跨越最近在辅导学生准备信息素养大赛时我反复琢磨了2025年复赛初中组那道“过山车‘峰’的个数问题”。这道题乍一看像是个简单的数学统计但真正动手实现时你会发现它巧妙地融合了数组遍历、逻辑判断和边界处理这几个C编程的核心基础特别适合用来检验初中生是否真正理解了如何将实际问题转化为计算机能执行的逻辑。题目本身描述并不复杂给你一个表示过山车轨道高度的整数序列你需要找出其中有多少个“峰”。这里的“峰”被定义为比它左右相邻点都高的点。听起来是不是很像地理课上学过的“山峰”没错这就是一个典型的一维“地形”分析问题。对于刚开始接触算法竞赛的初中生来说这道题的价值在于它避开了复杂的动态规划或高级数据结构而是把考察重点放在了基本功的扎实程度上。很多同学在初学编程时会过分追求“炫技”使用一些自己还没完全吃透的语法或库函数却忽略了像数组下标操作、循环控制和条件分支这些最基础、也最容易出错的部分。这道“过山车”题恰恰就是检验这些基本功的“试金石”。它要求你清晰地定义何为“峰”严谨地处理序列的开头和结尾因为两端的点没有完整的左右邻居然后准确无误地遍历整个数组并完成计数。这个过程正是计算思维中“分解问题、模式识别、抽象化、算法设计”的完美体现。我之所以想详细拆解这道题是因为在多年的教学和参赛指导中我发现许多同学在类似题目上丢分往往不是不会做而是栽在了细节上。比如循环变量是从1开始还是从0开始判断条件怎么写才能既简洁又覆盖所有情况如何处理输入输出才能符合在线评测系统的要求这些看似琐碎的“坑”恰恰是区分普通练习者和竞赛选手的关键。接下来我就把自己对这道题的解题思路、代码实现、以及那些容易踩坑的细节毫无保留地分享出来。无论你是正在备赛的学生还是希望巩固基础的编程爱好者相信这篇详尽的解析都能让你有所收获。2. 问题核心理解“峰”的定义与边界条件2.1 “峰”的数学化定义与逻辑转化题目给出的“峰”的定义非常直观对于一个整数序列中的某个位置i的元素height[i]如果它同时满足height[i] height[i-1]且height[i] height[i1]那么它就是一个峰。这个定义本身不难理解难点在于如何用C代码毫无歧义地表达出来并且处理好一些特殊情况。首先我们需要将文字定义转化为逻辑条件。在C中这通常用一个if语句来实现if (height[i] height[i-1] height[i] height[i1]) { peakCount; // 峰的数量加1 }这行代码就是整个算法的核心判断逻辑。但是直接这样写会立刻遇到一个问题当i是序列的第一个元素i0或最后一个元素时height[i-1]或height[i1]是不存在的访问它们会导致数组越界这是运行时错误程序会崩溃。因此我们的遍历范围不能包含首尾两个元素。对于一个长度为n的数组有效的、可能成为峰的内部位置索引是从1到n-2。这是解决本题的第一个关键点也是很多初学者容易忽略的边界条件。2.2 边界情况的深度剖析与处理策略边界处理是算法题目中最考验思维严谨性的地方。对于这道题边界情况非常明确序列长度不足3如果整个过山车轨道只有1个或2个点根据定义不可能存在同时拥有左右邻居且比它们都高的点。因此当n 3时答案直接就是0。这是一个有效的优化也是逻辑上的必须判断可以避免后续不必要的计算。遍历起止点的确定正如上面分析的我们不能检查height[0]和height[n-1]是否为峰因为它们缺少一边的邻居。所以循环变量i的初始值应为1终止条件应为i n-1即i n-2。用for (int i 1; i n - 1; i)这个循环结构是恰到好处的。相邻点高度相等的情况题目定义是“比左右相邻点都高”这意味着严格大于。如果出现相邻点高度相等例如序列[1, 2, 2, 1]中间的2虽然不比右边的2高所以它不是峰。我们的判断条件已经天然处理了这种情况无需额外考虑“大于等于”。注意有些同学可能会纠结如果连续三个点一样高或者出现“平台”怎么办题目定义的“峰”是严格的局部最大值点。在连续相等的平台中没有任何一个点能满足“比左右都高”的条件因此平台不会贡献任何峰。这一点需要理解透彻不要自己附加条件。2.3 输入输出格式的标准化处理信息素养大赛等在线评测系统Online Judge, OJ对输入输出格式有严格规定。通常这类题目的输入格式是第一行一个整数n代表序列长度第二行n个整数代表序列的具体值。输出格式是一个整数代表峰的个数。在C中标准做法是使用cin和cout进行输入输出。为了提高效率尤其是在大数据量时虽然本题数据量不大可以在一开始加上ios::sync_with_stdio(false);和cin.tie(0);来解除C和C的输入输出流之间的同步加快速度。这是一个在竞赛编程中很常见的小技巧。#include iostream #include vector // 或者使用普通数组 using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; // 方法一使用vector动态数组更安全方便 vectorint height(n); for (int i 0; i n; i) { cin height[i]; } // ... 计算峰数量的逻辑 cout peakCount endl; return 0; }使用vector的好处是无需手动管理内存且size()方法获取长度方便。当然用普通数组int height[1005];假设n最大为1000也是完全可行的更适合刚学数组不久的同学理解。3. 算法设计与代码实现详解3.1 完整算法流程步骤拆解在彻底理解了问题定义和边界条件后我们可以梳理出一个清晰、步骤化的算法流程。这个过程就像建造过山车之前先画好设计图每一步都要稳扎稳打。数据输入首先读取整数n代表轨道监测点的数量。接着读取n个整数存储到数组height中。这里存储结构的选择vector或普通数组取决于个人习惯和题目可能的数据范围。对于初中组竞赛数据量通常不会太大两者皆可。边界预判在开始核心计算前先进行预判。如果n 3那么直接输出0并结束程序。这是一个有效的“短路”操作既符合逻辑也提升了程序在极端情况下的效率。初始化计数器定义一个整型变量peakCount初始值设为0。这个变量将用来累加我们找到的峰的数量。核心遍历与判断使用一个for循环让循环变量i从1遍历到n-2C中写作i 1; i n-1; i。在循环体内对每一个i检查条件height[i] height[i-1] height[i] height[i1]是否成立。如果条件成立说明height[i]是一个峰执行peakCount。结果输出循环结束后peakCount中存储的就是最终的答案。使用cout将其输出即可。这个流程逻辑严密没有冗余步骤。它完美地体现了“遍历检查”这一朴素而强大的算法思想。对于初中生而言能将这个流程用代码准确无误地实现出来就已经达到了本题的考核要求。3.2 两种经典的代码实现版本下面我给出两个版本的完整代码实现。版本一使用vector更现代、更安全版本二使用普通数组更贴近C语言基础便于理解内存布局。版本一使用vector容器推荐#include iostream #include vector using namespace std; int main() { // 加速输入输出 ios::sync_with_stdio(false); cin.tie(0); int n; cin n; // 特殊情况处理点数少于3不可能有峰 if (n 3) { cout 0 endl; return 0; // 直接结束程序 } vectorint height(n); for (int i 0; i n; i) { cin height[i]; } int peakCount 0; // 遍历内部点索引从1到n-2 for (int i 1; i n - 1; i) { if (height[i] height[i - 1] height[i] height[i 1]) { peakCount; } } cout peakCount endl; return 0; }版本二使用普通静态数组#include iostream using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; if (n 3) { cout 0 endl; return 0; } // 假设题目中n的最大值不超过1000这里分配1005个空间以防万一 const int MAX_N 1005; int height[MAX_N] {0}; // 初始化数组为0是个好习惯 for (int i 0; i n; i) { cin height[i]; } int peakCount 0; for (int i 1; i n - 1; i) { if (height[i] height[i - 1] height[i] height[i 1]) { peakCount; } } cout peakCount endl; return 0; }两个版本的核心逻辑完全一致。vector版本更简洁无需关心最大数据范围数组版本则更基础。在竞赛中如果题目未给出n的范围使用vector是更稳妥的选择。3.3 关键代码段解析与编程技巧循环条件的写法for (int i 1; i n - 1; i)。这里i n - 1确保了i最大取到n-2因为当i等于n-1时循环条件不成立循环结束。这是C中表示左闭右开区间[1, n-1)的标准写法非常优雅地覆盖了所有内部点。条件判断的优化判断语句if (height[i] height[i - 1] height[i] height[i 1])中使用了逻辑与。是短路运算符即如果第一个条件height[i] height[i-1]不成立计算机就不会再去计算第二个条件这虽然对本题性能影响微乎其微但体现了良好的编程习惯。i与i在for循环的更新部分我使用了前置自增i。对于内置类型如int它与后置自增i在效果上没有区别。但在C习惯和某些情况下i被认为效率稍高对于迭代器对象而言所以在循环中习惯性使用i是一个不错的实践。变量命名使用peakCount、height这样具有明确意义的变量名而不是简单的cnt、a能极大提高代码的可读性尤其是在调试或回顾代码时。4. 从解题到举一反三算法思维的延伸训练4.1 变式思考如果问题定义改变怎么办一道好的题目其价值不仅在于解决它本身更在于它能引发一系列的思考。掌握了“找峰”之后我们可以尝试改变一下问题的定义看看算法该如何调整这能极大地锻炼我们的思维灵活性。变式一寻找“谷”Valley如果题目改为寻找“谷”即比左右相邻点都低的点算法需要如何修改 答案非常简单只需要把判断条件中的大于号改为小于号即可if (height[i] height[i - 1] height[i] height[i 1]) { valleyCount; }边界处理和遍历范围完全不变。这个变式帮助我们理解算法的框架输入、遍历、边界往往是稳定的核心逻辑判断条件根据问题定义而变化。变式二寻找“峰”或“谷”极值点如果题目要求统计所有“极值点”即峰或谷又该如何 这时我们需要在循环内部进行两次判断满足其一即可if ((height[i] height[i - 1] height[i] height[i 1]) || (height[i] height[i - 1] height[i] height[i 1])) { extremeCount; }注意这里使用了逻辑或||来连接两个条件。同样||也是短路运算符。变式三处理“平台”边缘假设我们修改“峰”的定义为“不小于左右相邻点”即height[i] height[i-1] height[i] height[i1]。这时在连续的平台[2,2,2]中中间的点是否算峰根据新定义它“不小于”左右等于所以算。但两边的点呢对于左边的2它不小于左边没有左边或视为无穷小不小于右边等于这需要重新定义边界。通常边界点只有一个邻居无法用“左右都不小于”来定义所以它们不算。这个变式引出了一个重要讨论问题定义的严谨性至关重要任何歧义都会导致程序无法编写。在竞赛中题目描述必须像原题那样毫无歧义。4.2 复杂度分析与算法优化空间探讨对于当前这道题我们采用的是一次线性扫描遍历算法的时间复杂度是O(n)其中n是序列的长度。这意味着计算时间随着数据量线性增长输入翻倍时间也大致翻倍。对于任何合理的n比如n 10^6这个速度都是瞬间完成的。空间复杂度方面我们使用了一个大小为n的数组来存储所有高度值因此空间复杂度是O(n)。这是必须的因为我们需要随机访问任何一个位置的前后元素。如果题目允许“流式”处理即边读入边判断我们是否可以优化空间呢理论上是可以的。我们只需要维护一个“滑动窗口”即可。具体来说我们同时只保留三个连续的高度值prev前一个curr当前next下一个。读入数据时我们依次更新这三个变量。当读入第i个点i 2即至少是第三个点时prev,curr,next分别对应height[i-2],height[i-1],height[i]。此时我们可以判断curr即height[i-1]是否为峰。这种方法可以将空间复杂度降低到O(1)即常数空间。但是对于初中组竞赛和本题而言我强烈不建议这样做。原因如下代码复杂度增加流式处理需要更精细的下标控制和变量更新逻辑容易出错。可读性下降代码不如数组版本直观不利于调试和他人阅读。收益甚微本题数据量不可能大到需要节省一个数组内存的地步。在竞赛中清晰、正确、易写的代码远比一点微小的空间优化重要。所以我们的O(n)空间解法就是本题的最优实践。它完美地平衡了效率、简洁性和可靠性。4.3 调试技巧与测试用例设计写完代码不代表万事大吉通过精心设计的测试用例来验证程序的正确性是编程中至关重要的一环。以下是我为这道题设计的一组测试用例覆盖了各种边界和特殊情况测试用例描述输入序列预期输出验证目的基础功能[1, 3, 2]1最简单的峰中间点无峰序列[1, 2, 3, 4, 5]0单调递增无峰多个峰[1, 3, 2, 5, 4, 6, 1]2位置1的3和位置4的5是峰边界长度[1, 2]0n3直接输出0最小长度[1]0n3直接输出0空序列0(然后无数字)0n0属于n3情况相邻相等[1, 2, 2, 1]0平台2,2不构成峰全相等[5, 5, 5, 5]0没有点比左右都高峰在开头[5, 4, 3]0开头点5没有左邻居不算峰峰在结尾[1, 2, 3]0结尾点3没有右邻居不算峰复杂序列[0, 1, 0, 2, 1, 2, 1, 0]2位置1的1和位置3的2是峰在你自己编写程序时一定要用类似这样的测试用例逐一验证。一个很好的方法是在本地编写一个简单的测试函数或者手动在脑子里模拟程序的运行过程称为“人肉调试”。确保你的程序对每一个用例都能给出正确答案你才能有信心提交。5. 备赛实战如何高效准备信息素养大赛算法题5.1 从“过山车”题看竞赛出题套路与考察重点通过对这道“过山车”问题的深度剖析我们可以窥见信息素养大赛尤其是初中组算法类题目的一些典型出题套路和考察重点问题背景生活化、趣味化“过山车”、“山峰”、“温度变化”、“股票波动”等都是将抽象的数组序列问题包装成生动的场景降低理解门槛激发兴趣。核心考察基础能力不追求高深的算法而是牢牢抓住数组操作、循环遍历、条件判断、边界处理这几项最最核心的编程基本功。题目本质是“披着故事外衣的数组遍历题”。强调逻辑严谨性边界条件序列头尾是天然的“陷阱”也是区分学生思维是否严密的关键。能否主动想到n3的情况是得分点之一。输入输出格式标准化严格遵循OJ的规范训练学生编写能够与评测系统交互的完整程序而不是一个孤立的函数。为更复杂问题奠基“找峰”问题是许多高级算法如寻找极值、信号处理中的峰值检测的简化版本。掌握它是学习更复杂序列分析的第一步。因此在备赛时与其好高骛远地去啃动态规划不如把类似这样的基础题目反复练习做到闭着眼睛也能写对。每一道题都要像我们刚才做的那样彻底吃透理解题意、设计算法、编写代码、测试调试、思考变式。5.2 针对初中组的备赛策略与资源推荐对于参加C初中组比赛的同学我结合多年经验给出以下备赛策略第一阶段巩固语言基础约1-2个月目标熟练掌握C的基本语法包括变量、数据类型、输入输出、条件语句if/else、循环语句for/while、数组、函数。方法找一本经典的入门教材如《C Primer Plus》前几章或完成一个系统的在线入门课程。关键是要动手写代码把书上的例子全部自己敲一遍并尝试修改。练习平台洛谷www.luogu.com.cn的“新手村”题目非常适合这个阶段。题目简单有趣有详细的题解和社区讨论。第二阶段专攻算法入门与模拟题约2-3个月目标熟悉竞赛常见的入门算法和思想如模拟、枚举、简单排序、字符串处理等。本道“过山车”题就属于“模拟”类。方法集中刷题。按照“模拟 - 枚举 - 排序 - 字符串”这样的专题进行。每道题都要追求独立完成调试通过后再去学习别人的优秀题解看看思路和代码有哪些可以优化的地方。资源推荐信息学奥赛一本通基础篇这本书的题目编排非常系统难度梯度合理。Codeforces的Div.3和Div.4轮次虽然这是国际平台但其Div.3和Div.4的前几道题难度与国内初中组复赛题相当是极好的练习材料。历年真题像“编程小伙伴测评网”这类网站收录了历年信息素养大赛的真题是最有针对性的练习材料。务必反复练习熟悉出题风格和难度。第三阶段模拟实战与错题复盘考前1个月目标提升解题速度和一次通过率锻炼比赛心态。方法进行限时模拟赛。找一套真题设定和正式比赛相同的时间如90分钟独立完成。赛后严格复盘哪道题卡住了卡住的原因是什么是题意理解错误、算法设计错误还是代码实现有bug把错题和难题整理到错题本上定期回顾。心态调整比赛时遇到不会的题很正常。合理分配时间先做有把握的题确保能拿的分都拿到。对于难题先写出暴力枚举的思路如果数据范围允许争取部分分数。记住竞赛不仅是比谁更聪明更是比谁更稳定、更细心。5.3 考场上的时间分配与代码规范建议当你在考场上打开这道“过山车”题时应该如何行动审题3-5分钟静下心来至少读两遍题目。用笔划出关键信息“整数序列”、“峰比左右相邻点都高”、“输出个数”。在脑子里构建几个简单的例子比如[1,3,2]输出1[1,2,3]输出0确保自己理解无误。审题的时间绝不能省理解偏差是导致WA错误答案的最常见原因。设计算法与伪代码2-3分钟在草稿纸上写下核心步骤输入n和数组 - 如果n3输出0 - 从i1到n-2循环 - 如果[i]比[i-1]和[i1]都大计数 - 输出计数。这个思考过程能帮你理清思路避免边写边想导致的混乱。编码实现5-8分钟按照伪代码在编程环境中一气呵成地写出代码。注意变量命名清晰缩进整齐。强烈建议写完立刻检查一遍重点检查循环的起止条件是否正确判断条件的大于号有没有写错输出的是不是最终答案的变量测试与调试3-5分钟使用题目给的样例输入进行测试。如果样例过了不要急着提交自己设计2-3个极端测试用例如n2全相等序列多个峰的序列进行验证。如果发现错误冷静地使用输出中间变量、或者小范围模拟运行的方法进行调试。提交与检查1分钟确认无误后提交。即使显示“Accepted”也可以考虑再看一眼代码有没有任何可以简化的地方虽然不要求但简洁优美的代码能减少自己复查时的脑力负担。关于代码规范在竞赛中不必追求工业级的完美但保持清晰可读至关重要适当的空格在运算符两边、逗号后面加空格如if (height[i] height[i-1])。一致的缩进使用4个空格或一个Tab进行缩进并全文保持一致。有意义的变量名用peakCount而不是c用height而不是a。写注释在关键步骤比如边界判断、核心循环前用一两行注释说明意图。这在调试和回顾时非常有帮助。这道“过山车‘峰’的个数问题”就像一块很好的磨刀石它不复杂但足够锋利能检验出你的编程基础是否扎实。把它吃透不仅能帮你在大赛中稳稳拿分更能让你建立起解决更复杂序列处理问题的信心和思维框架。编程学习就是一个这样不断拆解问题、严谨实现、反复调试的过程。当你通过自己的思考和实践让程序成功运行并得出正确结果时那种成就感正是编程最大的乐趣之一。