CCF CSP认证的题库里，第一题基本就是给考生“热身”用的，难度不高但很有代表性。201604-1折点计数就是其中一道非常典型的序列处理题，题目短、逻辑直白，拿满分几乎是标配。但正因为简单，很多人在刷题时容易一带而过，反而错过了一些值得沉淀的处理思路和边界细节。这篇文章就把这道题从头到尾拆开揉碎讲一遍，从题目理解、建模思路、代码实现到测试用例和常见坑，希望对正在备赛或者刚接触算法题的同学有点帮助。

1. 题目解析：折点计数的考点与得分策略

1.1 原题描述回顾与核心考点拆解

先说题目本身。输入首先是一个整数 n，表示序列的长度，第二行给出 n 个整数，构成一个一维序列。要求输出的结果是这个序列中“折点”的数量。什么叫折点？题目的定义很直白：如果一个数比它前一个数大、同时又比它后一个数大，或者比它前一个数小、同时又比它后一个数小，那这个位置就是一个折点。说白了，这个数在局部范围内是一个“峰”或者一个“谷”——它打破了前后两个方向的单调趋势。

考点其实就两个：第一，你能不能准确把“折点”这个文字定义转换成代码里的判断条件；第二，你能不能正确处理边界元素。第一点对应的是基本的逻辑转化能力，第二点考察的是对“中间元素”这个概念的理解。题目不会绕弯子，不涉及排序、查找、动态规划这些进阶内容，完全是入门级的数组遍历。但它的价值在于：这是序列处理类题目最基础的形态，后面很多复杂题目的核心判断逻辑，本质上都是从“比较相邻元素关系”延伸出来的。

1.2 为什么这道题值得认真做一遍

有的同学可能会想，这种题我闭着眼睛都能AC，还需要专门分析吗？我的看法是，简单题恰恰是建立“做题手感”的最好材料。你在简单题里养成的习惯——比如先画清楚边界、先写测试用例再写代码、先考虑清楚相等元素的处理——会在做中等题和难题时救你很多次。

尤其是CSP认证这种考试环境，第一题拼的其实是“稳”。你要做到的不只是AC，而是快速、准确、一次提交就过。很多人在考场上第一题因为下标越界、忘记特判、循环边界写错等低级失误反复提交，既浪费时间又影响心态。折点计数这道题，就是练习“一次写对”思维的好素材——它的逻辑够简单，让你有精力去关注代码之外的思考过程：输入范围、循环边界、特殊情况，这些都是考试中更重要的东西。

2. 序列处理的建模思路：从折点定义到判定条件

2.1 折点的数学表达与单调性视角

要写好这道题，第一步不是急着写循环，而是把“折点”翻译成更数学化的表达。任意取序列中的一个中间位置 i，它前后有 a[i-1]、a[i]、a[i+1] 三个连续元素。如果 a[i] 同时大于两边，那它是一个局部峰值；如果同时小于两边，那它是一个局部谷值。两种情况都满足“折点”的定义。

如果换个角度看，把序列看成一段一段的“上升”和“下降”拼接起来，那么折点就是单调性发生改变的位置。用差值来表示：d1 = a[i] - a[i-1]，d2 = a[i+1] - a[i]。如果 d1 和 d2 一正一负，说明序列在 i 这里从上升变成下降，或者从下降变成上升，折点成立。用数学式表达就是 d1 * d2 < 0。这个形式非常干净，而且天然避开了“相等”的争议——只要 d1 或 d2 等于0，乘积就是0，不满足严格小于0，i 就不会被计为折点。

但这个“差值异号”的公式有一个前提需要考虑：如果序列中存在相等的相邻元素，行为是否符合题目意图？从定义上看，题目说“比前一个数大而比后一个数小，或者比前一个数小而比后一个数大”，已经隐含了严格大于和严格小于，所以相等的情况自然不属于折点。乘积写法与直接比较写法在这种情形下结果一致，两种思路最终殊途同归。

2.2 首尾元素为什么不参与计数

这是题目里一个非常关键的隐含条件。折点的定义需要比较“前一个数”和“后一个数”，而序列的第一个元素没有前一个数，最后一个元素没有后一个数。因此，它们不可能成为折点。这也是为什么循环范围只需要从第二个元素遍历到倒数第二个元素，而不是从头遍历到尾。

很多第一次做这道题的同学栽就栽在循环范围上。有人把循环写成从0到n-1，然后访问a[i-1]或者a[i+1]的时候直接越界，程序跑起来可能报错，也可能静默访问到内存里的垃圾值，结果完全不可控。还有人意识到首尾不用考虑，但循环写成从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[i+1]) 或者 (a[i] < a[i-1] && a[i] < a[i+1]): count = count + 1 输出 count

这个思路非常符合直觉：你不是在分析整个序列的波峰波谷，而是活在“当下”，只关心以当前元素为中心的局部三点关系。这种方式实现起来没有一丁点多余的动作，每判断一个位置只需要两次比较（或者用乘积写法，一次乘法加一次比较），时间开销极小。

为什么值得强调“三元组”这个词？因为很多序列处理题目，尤其是涉及局部特征判定的题目，本质上都是“滑窗”思想的微缩版。你在这个简单题里形成的“取连续k个元素、判断中心特征”的思维模式，到了判断回文子串、滑动窗口最大值、连续子数组等问题时依然适用。基础题的真正价值，往往体现在这种思维迁移上。

3.2 另一种视角：差分符号变化检测

除了直接比较大小，还可以先预处理出差值数组 d[i] = a[i] - a[i-1]，然后统计 d[i] 与 d[i+1] 符号相反的位置数量。用文字来描述就是：如果相邻两个差值的乘积小于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[i+1]) > 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 结束，也就是 i=1、2、3，一共检查三个位置，完美覆盖所有中间元素。跑完样例没问题后，再想几个特殊用例：

• 全是递增序列1 2 3 4 5，输出0；
• 全是递减序列5 4 3 2 1，输出0；
• 有平台（相等元素）的序列1 3 3 2，3和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[i+1]) || (a[i] < a[i-1] && a[i] < a[i+1])) { 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[i+1]) or (a[i] < a[i-1] and a[i] < a[i+1]): count += 1 print(count)

Python在CSP考试中也是允许的，但第一题数据量一般不大，Python跑起来没压力。不过要注意的是，如果n为0或者输入不完整，input().split()可能拿不到足够的数字，因此在本地调试时要保证输入格式正确。CSP的评测数据通常规范，不会给你格式错误的输入，所以正常写就行。

5. 测试用例与调试技巧实录

5.1 不只是样例：多组边界用例的构造

前面提到了一些测试用例，这里系统整理一下。做OJ题目时，很多人拿到题直接看样例，样例过了就交，结果经常在隐藏数据上翻车。其实对于你来说，多花五分钟构造几个边界用例，远比反复提交等评测结果更省时间。

针对折点计数，我建议至少测试下面几类输入：

构造锯齿序列那组用例时，我们来数一下：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[i+1]，第一个元素就越界访问a[-1]。也有些人虽然起点为1，但终点写成i < n，跑到最后一个元素时访问了a[n]。这两个错误在有些编译器上不一定会立刻报错，但会读入随机值，导致输出结果时对时错，极具迷惑性。排查方法很简单：把循环改成for (int i = 1; i < n - 1; i++)，从此再也不用担心首尾越界。

第二，相等元素的处理。有的同学理解的折点是“趋势改变”，于是写成(a[i] - a[i-1]) * (a[i+1] - 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题，不管多简单，都留出几分钟在草稿纸上写下这道题你踩过或者可能踩的坑。比如这里就是“循环边界”和“严格比较”。日积月累，你会发现很多题目的坑是有共性的，而你自己的易错清单会越来越长，也越来越具体。到了真正考试时，你的那份清单会比任何模板都更管用。折点计数这道题，就是这份清单的第一行。