CSP 201604-1折点计数：抓住序列处理与边界思维的要点

CCF CSP认证的题库里第一题基本就是给考生“热身”用的难度不高但很有代表性。201604-1折点计数就是其中一道非常典型的序列处理题题目短、逻辑直白拿满分几乎是标配。但正因为简单很多人在刷题时容易一带而过反而错过了一些值得沉淀的处理思路和边界细节。这篇文章就把这道题从头到尾拆开揉碎讲一遍从题目理解、建模思路、代码实现到测试用例和常见坑希望对正在备赛或者刚接触算法题的同学有点帮助。1. 题目解析折点计数的考点与得分策略1.1 原题描述回顾与核心考点拆解先说题目本身。输入首先是一个整数 n表示序列的长度第二行给出 n 个整数构成一个一维序列。要求输出的结果是这个序列中“折点”的数量。什么叫折点题目的定义很直白如果一个数比它前一个数大、同时又比它后一个数大或者比它前一个数小、同时又比它后一个数小那这个位置就是一个折点。说白了这个数在局部范围内是一个“峰”或者一个“谷”——它打破了前后两个方向的单调趋势。考点其实就两个第一你能不能准确把“折点”这个文字定义转换成代码里的判断条件第二你能不能正确处理边界元素。第一点对应的是基本的逻辑转化能力第二点考察的是对“中间元素”这个概念的理解。题目不会绕弯子不涉及排序、查找、动态规划这些进阶内容完全是入门级的数组遍历。但它的价值在于这是序列处理类题目最基础的形态后面很多复杂题目的核心判断逻辑本质上都是从“比较相邻元素关系”延伸出来的。1.2 为什么这道题值得认真做一遍有的同学可能会想这种题我闭着眼睛都能AC还需要专门分析吗我的看法是简单题恰恰是建立“做题手感”的最好材料。你在简单题里养成的习惯——比如先画清楚边界、先写测试用例再写代码、先考虑清楚相等元素的处理——会在做中等题和难题时救你很多次。尤其是CSP认证这种考试环境第一题拼的其实是“稳”。你要做到的不只是AC而是快速、准确、一次提交就过。很多人在考场上第一题因为下标越界、忘记特判、循环边界写错等低级失误反复提交既浪费时间又影响心态。折点计数这道题就是练习“一次写对”思维的好素材——它的逻辑够简单让你有精力去关注代码之外的思考过程输入范围、循环边界、特殊情况这些都是考试中更重要的东西。2. 序列处理的建模思路从折点定义到判定条件2.1 折点的数学表达与单调性视角要写好这道题第一步不是急着写循环而是把“折点”翻译成更数学化的表达。任意取序列中的一个中间位置 i它前后有 a[i-1]、a[i]、a[i1] 三个连续元素。如果 a[i] 同时大于两边那它是一个局部峰值如果同时小于两边那它是一个局部谷值。两种情况都满足“折点”的定义。如果换个角度看把序列看成一段一段的“上升”和“下降”拼接起来那么折点就是单调性发生改变的位置。用差值来表示d1 a[i] - a[i-1]d2 a[i1] - a[i]。如果 d1 和 d2 一正一负说明序列在 i 这里从上升变成下降或者从下降变成上升折点成立。用数学式表达就是 d1 * d2 0。这个形式非常干净而且天然避开了“相等”的争议——只要 d1 或 d2 等于0乘积就是0不满足严格小于0i 就不会被计为折点。但这个“差值异号”的公式有一个前提需要考虑如果序列中存在相等的相邻元素行为是否符合题目意图从定义上看题目说“比前一个数大而比后一个数小或者比前一个数小而比后一个数大”已经隐含了严格大于和严格小于所以相等的情况自然不属于折点。乘积写法与直接比较写法在这种情形下结果一致两种思路最终殊途同归。2.2 首尾元素为什么不参与计数这是题目里一个非常关键的隐含条件。折点的定义需要比较“前一个数”和“后一个数”而序列的第一个元素没有前一个数最后一个元素没有后一个数。因此它们不可能成为折点。这也是为什么循环范围只需要从第二个元素遍历到倒数第二个元素而不是从头遍历到尾。很多第一次做这道题的同学栽就栽在循环范围上。有人把循环写成从0到n-1然后访问a[i-1]或者a[i1]的时候直接越界程序跑起来可能报错也可能静默访问到内存里的垃圾值结果完全不可控。还有人意识到首尾不用考虑但循环写成从1到n-1漏掉了倒数第二个位置导致少统计了一个可能的折点。这两种都是边界处理不严谨的表现。在考试或者平时刷题时我的习惯是先数清楚n个元素的数组下标是0到n-1中间元素的下标是1到n-2。用C/C写循环就是 for (int i 1; i n - 1; i)这个范围一根筋到底不需要任何额外判断。如果你是直接用样例在心里跑一遍会发现这个范围正好覆盖了所有可能的位置。2.3 边界情况的处理原则一个序列最少有几个元素题目输入里 n 是正整数但如果 n 3序列中根本不存在“既有前一个又有后一个”的元素折点数量必然是0。你写的程序能否正确处理这种情况如果你的循环写的是 for (int i 1; i n - 1; i)那么当 n 2 时循环条件 1 1 不成立当 n 1 时 1 0 也不成立。程序自动跳过循环输出0。这说明只要循环范围本身正确极端输入不需要特判也能安全通过。不过这并不代表你可以完全不关心输入范围。有些评测系统对 n 的最大值有明确的约束比如 n ≤ 1000那数组开到1005或1010就够了如果约束是 n ≤ 100000就得开100005或更大。多开一点点空间是写竞赛代码的好习惯宁可多开一点也不要卡着边界开数组否则遇到边界数据容易出问题。这道题的 n 上限按CSP第一题的习惯一般不会太大但养成这个习惯对你后面做其他题目有益无害。3. 算法设计与复杂度分析3.1 直接遍历的三元组判定法这道题最直接的做法就是一次遍历每次取连续三个元素判断中间元素是否满足折点条件。伪代码可以写成下面这样输入 n 输入数组 a[0..n-1] count 0 for i 1 to n-2: if (a[i] a[i-1] a[i] a[i1]) 或者 (a[i] a[i-1] a[i] a[i1]): count count 1 输出 count这个思路非常符合直觉你不是在分析整个序列的波峰波谷而是活在“当下”只关心以当前元素为中心的局部三点关系。这种方式实现起来没有一丁点多余的动作每判断一个位置只需要两次比较或者用乘积写法一次乘法加一次比较时间开销极小。为什么值得强调“三元组”这个词因为很多序列处理题目尤其是涉及局部特征判定的题目本质上都是“滑窗”思想的微缩版。你在这个简单题里形成的“取连续k个元素、判断中心特征”的思维模式到了判断回文子串、滑动窗口最大值、连续子数组等问题时依然适用。基础题的真正价值往往体现在这种思维迁移上。3.2 另一种视角差分符号变化检测除了直接比较大小还可以先预处理出差值数组 d[i] a[i] - a[i-1]然后统计 d[i] 与 d[i1] 符号相反的位置数量。用文字来描述就是如果相邻两个差值的乘积小于0说明趋势反转这里就是一个折点。这种写法有什么好处主要在于逻辑更贴近“单调性改变”这个本质。当你面对的问题不只是“统计折点个数”而是“找出所有折点位置”或者“把序列分割成若干单调段”时差值视角会让你更容易扩展。比如你要输出所有折点所在的下标直接比较法也能做到但差值法会让你一眼看出分段的边界在哪里。从代码量来看两种写法差别很小。直接比较法不需要额外数组差值法需要先遍历一次生成差值数组多了一次 O(n) 的操作但复杂度量级没有变化。实际做题时我建议你按自己最不容易写错的方式来实现——考试最重要的是结果正确不是写法酷炫。如果你对“差值异号”这个公式足够熟悉用它也行如果你觉得直接写大于小于更放心那也完全可以。两种方案在思路上互为印证理解了它们你对这道题的理解就立体了。3.3 时间复杂度与空间复杂度讨论无论是直接遍历还是差值法都只需要对序列进行一次或两次线性扫描时间复杂度是 O(n)。空间方面直接比较法只需要存储原始数组额外空间 O(1)差值法需要额外的差值数组空间 O(n)。对于CSP第一题的输入规模来说这个复杂度远远够用。你可能会想既然复杂度这么低那是不是意味着这道题没有优化空间也没有优化的必要答案是——确实没有优化的必要。O(n) 已经是最低时间复杂度了因为你至少要读入 n 个整数才能判断它们的相对大小。在同类题目里凡是需要比较所有相邻元素的复杂度下界就是 O(n)。真正的考察重点不在于你能不能发明更快的算法而在于你能不能把 O(n) 的写法一次写对、不遗漏边界。所以在刷题时我不建议在这种题目上追求“骚操作”。老老实实遍历、用最简单的逻辑判断就是最高效的得分策略。把省下来的脑力留给后面的题目才是整体利益最大化的选择。4. 代码实现与关键代码讲解4.1 C语言实现推荐写法C语言是CSP认证考场上的主流选择原因只有一个稳定、可控。下面给出完整可运行的代码#include stdio.h int main() { int n; scanf(%d, n); int a[1005]; for (int i 0; i n; i) { scanf(%d, a[i]); } int count 0; for (int i 1; i n - 1; i) { if ((a[i] a[i - 1] a[i] a[i 1]) || (a[i] a[i - 1] a[i] a[i 1])) { count; } } printf(%d\n, count); return 0; }这段代码的几个细节值得说道说道。数组大小开成1005而不是精确的1000是一个刻意留出的余量目的就是防止下标越界。可能有人会问我访问的下标最大是 n-1为什么还要多开5个原因很简单如果你在循环或者后续调试中不小心把下标写成了 n比如访问了 a[n]而数组大小恰好是1000那么这次访问就越界了。你多开几个元素越界后可能只是读到无害数据不至于马上导致段错误至少给程序多一些容错空间。当然这不能替代正确的边界判断但多开一点总没有坏处。判断条件里用括号把两个比较表达式分别包起来再用逻辑或连接清晰明了。有些同学喜欢写成乘积形式if ((a[i] - a[i-1]) * (a[i] - a[i1]) 0)这个写法把“中间元素同时大于两边或者同时小于两边”表现为“两个差值同号”。这个公式也成立而且更短。但要注意乘法结果可能超出int范围吗a[i] 的值如果到10^9级别差值可能在 2*10^9 量级两个差值乘起来会超过 int 上限导致溢出。而直接比较大小的写法完全没有这个风险。这是我个人更推荐直接比较的原因之一。4.2 怎样保证一次编译通过、一次提交通过“一次通过”不是靠运气而是靠动手前的思考。我的习惯是写代码之前先在草稿纸上把样例跑一遍确认自己对题意的理解没有偏差。拿官方样例来说输入是7\n5 4 1 2 6序列是 5 4 1 2 6。从第二个位置下标1开始检查4 比5小、比1大不是折点1 比4小、比2小是折点2 比1大、比6小是折点。所以答案是2。代码跑出来的结果应该正好是2。如果你拿这个样例去验证自己的循环边界i从1开始到 n-2 5 结束也就是 i1、2、3一共检查三个位置完美覆盖所有中间元素。跑完样例没问题后再想几个特殊用例全是递增序列1 2 3 4 5输出0全是递减序列5 4 3 2 1输出0有平台相等元素的序列1 3 3 23和3重复中间不存在严格峰谷输出0锯齿序列1 3 2 4 3输出4。这些用例在设计时不是为了凑数而是为了把你的实现逼到正确的边界上。递增递减验证“无折点”的情形相等元素验证“严格大于/小于”的定义锯齿序列验证统计是否精确。有了这个测试用例集你在提交之前就会很有底气而不是心里发虚地交上去赌评测数据。4.3 C与Python实现的简要对比C版本的思路完全一样只是输入输出上可以选cin/cout也可以为了性能用scanf/printf#include iostream using namespace std; int main() { int n; cin n; int a[1005]; for (int i 0; i n; i) { cin a[i]; } int count 0; for (int i 1; i n - 1; i) { if ((a[i] a[i-1] a[i] a[i1]) || (a[i] a[i-1] a[i] a[i1])) { count; } } cout count endl; return 0; }CSP认证对C的代码通常没有性能压力第一题的输入量很小cin加ios::sync_with_stdio(false)完全够用。不过有些选手习惯了C的输入输出也不觉得别扭那就继续用。考试选自己最熟的工具就好千万不要在考场上尝试平时没用过的输入输出方式。Python版本就更加简洁适合用来验证思路n int(input()) a list(map(int, input().split())) count 0 for i in range(1, n - 1): if (a[i] a[i-1] and a[i] a[i1]) or (a[i] a[i-1] and a[i] a[i1]): count 1 print(count)Python在CSP考试中也是允许的但第一题数据量一般不大Python跑起来没压力。不过要注意的是如果n为0或者输入不完整input().split()可能拿不到足够的数字因此在本地调试时要保证输入格式正确。CSP的评测数据通常规范不会给你格式错误的输入所以正常写就行。5. 测试用例与调试技巧实录5.1 不只是样例多组边界用例的构造前面提到了一些测试用例这里系统整理一下。做OJ题目时很多人拿到题直接看样例样例过了就交结果经常在隐藏数据上翻车。其实对于你来说多花五分钟构造几个边界用例远比反复提交等评测结果更省时间。针对折点计数我建议至少测试下面几类输入用例类型输入示例预期结果测试目的官方样例7 / 5 4 1 2 62基准验证单调递增5 / 1 2 3 4 50无折点单调递减5 / 5 4 3 2 10无折点相等元素5 / 1 3 3 2 41严格比较平台不算折点锯齿序列6 / 1 3 2 4 3 54每个中间元素都是折点最小长度3 / 1 2 30只有首尾无折点波峰开头5 / 3 5 1 2 01首尾不计认定中间折点构造锯齿序列那组用例时我们来数一下3个连续元素 (1,3,2) 中3是峰计数1(3,2,4) 中2是谷计数2(2,4,3) 中4是峰计数3(4,3,5) 中3是谷计数4。所以答案是4。这个用例能测出你的循环是否完整遍历了所有中间位置。如果少一个结果就变成3循环边界的问题立刻暴露。这个表虽然简单但每一类都有它存在的意义。你如果每次做题都按照“样例、单调、相等、锯齿、最小长度”这几个维度去构造用例一段时间后会形成很强的边界敏感度写代码时就会下意识地避开那些坑。5.2 常见错误与排查心得根据我自己的踩坑经历和帮别人调代码的经验这道题最常见的错误集中在三个地方。第一循环范围写错。这是最普遍的有人写成for (int i 0; i n; i)然后判断里还要访问a[i-1]和a[i1]第一个元素就越界访问a[-1]。也有些人虽然起点为1但终点写成i n跑到最后一个元素时访问了a[n]。这两个错误在有些编译器上不一定会立刻报错但会读入随机值导致输出结果时对时错极具迷惑性。排查方法很简单把循环改成for (int i 1; i n - 1; i)从此再也不用担心首尾越界。第二相等元素的处理。有的同学理解的折点是“趋势改变”于是写成(a[i] - a[i-1]) * (a[i1] - a[i]) 0或者使用之类的非严格判断这就把相等的情况也算了进去。比如序列1 2 2 3中间两个2都不是严格峰谷但如果用非严格判断可能把第一个2或第二个2误判成折点。题目要求的是严格大于、严格小于判断时一定要用和而不是和。第三数组开得太小。有人根据 n 的最大值直接开int a[1000]以为刚刚好。但C语言中合法的下标范围是0到999如果你访问a[1000]已经越界而多开几个空间就能避免这类问题。我一般习惯多开5到10个元素这基本上是竞赛选手的标配操作。虽然这道题数据弱多开几个看似没必要但养成习惯后将来做其他题时你不会因为这种低级失误卡住。还有一个小细节输出格式。题目要求输出一个整数不要输出多余的文字不要加换行之外的空格。有的同学在本地测试时喜欢加“答案是”这样的提示交上去之前忘了删掉结果格式错误分就没了。提交之前扫一眼自己的printf或cout确保输出的内容只有你需要的那部分。5.3 现场调试的节奏建议真正到了考场或者OJ上反复出问题的时候节奏很重要。我的建议是第一次写完代码后先不要急着提交花两分钟用三种用例验证——样例、单调序列、锯齿序列。如果三个都过了再花30秒检查循环边界和输出格式然后提交。这样做看起来“浪费”了两三分钟但实际能够有效降低你因为低级错误反复提交的概率。CSP认证是有时间限制的每道题如果都能一次通过你就有更多时间去做后面的题目这种策略性节奏比盲目刷题重要得多。6. 从折点计数延伸开去序列特征提取的常见套路6.1 信号处理中的峰值谷值检测思路折点这个词在算法题里可能有点陌生但如果你接触过信号处理、数据分析或者量化交易里的“波峰波谷检测”就会发现它们本质上是同一个问题。给一段离散的信号序列找局部极大值、局部极小值就是找折点的位置。区别只在于折点计数只统计个数而实际应用中往往还需要判断峰的显著程度、谷的深度甚至过滤掉噪声产生的微小波动。从这个角度来看题目虽然简单但它把一个非常底层的序列特征提取手段带到了你面前。你将来写一个简单的股票数据波动分析、传感器数据异常检测或者音频波形特征提取的小程序都会遇到类似的判断“这个点是不是比两边都高/低”。那时候你会发现这里的核心逻辑跟201604-1折点计数如出一辙。这就是基础题的价值它不炫技但它是你在真实世界里解决问题时用得最频繁的那把螺丝刀。6.2 单次遍历思想的延伸再往深处想一步折点计数的核心是“通过局部关系判断全局特征”这种思想在很多进阶题目里以各种变体出现。比如“最大连续上升子段”需要你在单次遍历中记录当前上升长度和最长上升长度本质上也是在使用相邻元素的大小关系。再比如“买卖股票的最佳时机”需要你在遍历过程中找到最低点和最高点避免重复扫描。还有“单调栈”类题目比如“下一个更大元素”可以在线性时间内维护一个单调的栈结构来求解很多问题的思路就来源于“序列极值具有局部判定特征”这一观察。所以不要觉得第一题跟后面的难题没关系。恰恰相反把第一题吃透、把“遍历过程中维护局部特征”这种思维刻进脑子里你后面遇到陌生题目时就会本能地去想能不能用一次遍历、用几个变量、用局部关系来解决很多时候答案就是这样浮现出来的。6.3 对后续CSP题目的启示CSP认证的命题风格比较固定前几题通常围绕模拟、字符串处理、基础数据结构展开而序列处理是出现频率极高的题材。折点计数只是其中一个非常小的切片。你可能在后面的题目里遇到“求序列中所有极值点的差值之和”“对序列进行平滑处理”这类变体到时候你会发现核心的遍历框架没有变变的只是判断条件和累积方式。我在备考时有个体会把历年的第一题、第二题拿出来横向对比往往能找到一些“祖传套路”。比如“读入数组→维护少量变量→线性扫描→输出结果”这套流程几乎可以覆盖CSP前两题80%的情况。折点计数就是这个流程最纯粹的代表作吃透它等于给后面几道题打了一个不错的地基。我个人在做这道题时其实更喜欢用差值符号突变来判断折点因为它更贴近“趋势反转”这个本质。但在给某位刚开始准备CSP的同学讲这道题时他会选择直接比较相邻元素大小的写法理由是更直白、不必担心乘法的溢出问题。这两种选择都没有错关键是你要找到自己最舒服、最不容易出错的方式并且在考试中坚持使用而不是在两种写法之间反复摇摆犹豫。最后再分享一个小技巧。每次做完一道OJ题不管多简单都留出几分钟在草稿纸上写下这道题你踩过或者可能踩的坑。比如这里就是“循环边界”和“严格比较”。日积月累你会发现很多题目的坑是有共性的而你自己的易错清单会越来越长也越来越具体。到了真正考试时你的那份清单会比任何模板都更管用。折点计数这道题就是这份清单的第一行。