华为OD机试双机位C卷里采样过滤这道题我刷完最大的感受是题目读起来像初中物理实验题写起来却非常考验状态建模能力。它给出一串传感器采样数据要求按区间的上下界和连续越界次数来过滤异常数据很多考生用C、Python、Java、JS、Go等语言写出的代码都不一样核心却只有一个——把正常/故障这两个隐含状态转成确定的逻辑分支。这道题适合准备华为OD机试的考生、想练多语言实现基本功的开发者以及那些看得懂题、写不对代码的刷题人。它不算难但边界条件很多稍不留神就会在恢复状态的有效数据计数上栽跟头。下面我把完整题面、状态机推导、五种语言实现和避坑清单一次性讲透代码可以直接抄作业。1. 题目场景与核心考点1.1 从传感器采样说起实际的数据采集系统里传感器不可能永远精准输出。某个瞬间受到干扰采样值可能跌破下限或者冲破上限。系统要做的事情很简单识别这些异常数据并且在异常连续出现到一定程度后认为设备不是偶发抖动而是真的出故障了。故障不是永久的等后续数据恢复正常范围并连续保持一段时间后系统又会自动认为设备已经恢复。注意这里的措辞不是看到一个正常数据就恢复而是连续看到足够数量的正常数据才恢复。这个连续是整个题目的灵魂也是很多人写错的地方。这道题考的就是把这个过程用程序模拟出来。它不是动态规划不是贪心也不涉及复杂的数据结构本质是一道按规则驱动的状态机模拟题。但正因为规则里面有连续计数、状态切换、恢复判定它非常容易在细节上出错。华为OD机试把它放在C卷里实际上是在考验候选人的工程直觉能否把自然语言描述的场景准确翻译成无歧义的代码逻辑。1.2 完整题面与输入输出约定我在刷题时还原的常见版本如下后续所有代码都基于这套约定。数据值处于区间 [Smin, Smax] 内视为有效数据低于 Smin 或高于 Smax 视为越界数据。系统初始处于正常状态。正常情况下如果连续出现 N 个越界数据系统进入故障状态并认为从这组连续越界数据的第一个开始设备已经故障。故障期间所有数据一律不作为有效数据统计。故障状态下一旦连续出现 N 个有效数据系统自动恢复恢复到正常状态的这一刻该有效数据本身也计入有效数据。请统计整段采样数据中处于正常状态下且为有效数据的个数。输入格式第一行三个整数Smin、Smax、N空格分隔。第二行一个整数M表示采样数据个数。第三行 M 个整数采样值序列。约束条件为1 ≤ M ≤ 1000001 ≤ N ≤ MSmin ≤ Smax所有采样值在 32 位整数范围内。输出格式一个整数表示正常状态下有效数据的个数。如果你刷到的原题在恢复瞬间的第N个有效数据是否计入这个问题上和我的约定不同代码只需要微调具体我在第4节里会单独说明这里先按最通行的版本走。1.3 样例推演给一个具体例子帮助理解。输入1 3 2 10 1 2 9 8 5 2 3 2 1 9一步步手工推演数据 1有效计入ans1连续越界计数归零。数据 2有效计入ans2。数据 9越界连续越界计数变成1。数据 8越界连续越界计数变成2达到 N2系统进入故障状态从数据 9 开始被认定为故障期间。数据 5越界故障中连续有效计数清零。数据 2有效故障中连续有效计数变成1。数据 3有效故障中连续有效计数变成2达到 N2系统恢复。该数据本身计入有效ans3。数据 2有效正常状态计入ans4。数据 1有效正常状态计入ans5。数据 9越界连续越界计数变成1但还没达到2所以不触发故障。最终输出 5。这个例子覆盖了偶发越界不触发故障连续越界触发故障故障恢复瞬间计数三个关键环节建议新手先把这个样例在纸上完整画一遍再往下看代码。2. 解题思路状态机建模是关键2.1 直接计数为什么不行最容易想到的笨办法是数一下总共有多少个越界数据然后拿总数据个数减去越界个数。但这样做完全错误因为题目要统计的是正常状态下的有效数据个数根本问题是故障期间连正常值都不算数。举一个反例Smin0Smax10N3序列为 1 2 3 99 99 99 4 5 6。越界数据只有 99 那三个看起来有效数据是 1 2 3 4 5 6 共 6 个。但按照规则连续三个 99 之后设备进入故障4 5 6 出现在故障期间虽然它们是有效范围内的值却不能被计入。真实答案应该是 1 2 3 这 3 个故障后的 4 5 6 只有等连续出现 3 个有效数据之后才恢复这个序列刚好在故障后只有 3 个有效数据恢复的那一瞬间可以计入一个也只是一个答案 4。如果写成代码时不区分是否处于故障状态而只看单个数据是否有效那么 4 5 6 会被全部计入直接多算 2 个。这类题目的所有坑几乎都集中在状态二字上。2.2 双状态与三个计数器的分工整个系统只需要两个状态正常态和故障态。区分这两个状态用布尔变量或者整型变量都可以我习惯用布尔值语义清晰。三个计数器各有分工errCnt正常态下的连续越界计数用于触发故障。okCnt故障态下的连续有效计数用于解除故障。ans最终有效数据累计值。注意 errCnt 和 okCnt 永远不会同时起作用。正常态下只用 errCnt故障态下只用 okCnt。每次状态切换时要把另一个计数器清零否则会出现残留计数导致误判。举一个典型错误写法正常状态遇到有效数据时只做了 ans忘记把 errCnt 清成 0。那么序列里有效-越界-有效-越界这种间隔越界会被错误累加最后明明没有连续越界却错误触发故障。这个清空动作必须跟状态转移严格绑定。2.3 状态转移与复杂度状态转移可以用一张表说清楚当前状态当前数据动作正常有效anserrCnt0状态不变正常越界errCnt若 errCntN状态切到故障okCnt0故障有效okCnt若 okCntN状态切到正常errCnt0ans故障越界okCnt0状态不变这里最容易被问住的是正常态下触发故障时要不要处理已经累计的 ans不需要。因为触发故障的那些数据本身是越界数据越界数据在正常情况下也不会被计入 ans所以故障发生后ans 保持原样即可。这与从这组连续越界的第一个开始就是故障并不矛盾因为越界数据本来就不是有效数据不存在把之前计入的扣回去的问题。时间复杂度是 O(M)只需要一趟遍历空间复杂度 O(M) 是因为要存储整个数据序列其实边读边处理也可以做到 O(1) 额外空间。但机试环境里读入整行再做 split 是主流习惯存储 M 个整数对 100000 这个量级完全没压力。3. 五种语言实现与细节对照3.1 C 版本C 是华为OD机试里最主流的提交语言之一主要留意整数溢出和输入效率。100000 个数据的量级下cin 其实够用但我还是建议加一句ios::sync_with_stdio(false)养成习惯。答案用 long long 而不是 int防止极端数据累加溢出。#include iostream #include vector using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int smin, smax, N; cin smin smax N; int M; cin M; vectorint data(M); for (int i 0; i M; i) { cin data[i]; } bool fault false; int errCnt 0; int okCnt 0; long long ans 0; for (int x : data) { bool valid (x smin x smax); if (!fault) { if (valid) { ans; errCnt 0; } else { errCnt; if (errCnt N) { fault true; okCnt 0; } } } else { if (valid) { okCnt; if (okCnt N) { fault false; errCnt 0; okCnt 0; ans; } } else { okCnt 0; } } } cout ans endl; return 0; }这段代码有几个 C 特有的细节vector 读入时直接用cin data[i]前提是前面关掉了同步for (int x : data)这种方式遍历比下标访问更简洁布尔值直接参与条件判断不需要写成 true之类的冗余形式。3.2 Python 版本Python 写这种模拟题最舒服逻辑直白不需要管类型声明但要注意输入读取的兼容性。第三行的 M 个整数理论上都在一行但有时候换行格式不标准稳妥做法是用sys.stdin.read()一次性读入所有 token再按顺序分配。import sys def solve(): tokens sys.stdin.read().split() idx 0 smin int(tokens[idx]); idx 1 smax int(tokens[idx]); idx 1 N int(tokens[idx]); idx 1 M int(tokens[idx]); idx 1 data list(map(int, tokens[idx:idx M])) fault False err_cnt 0 ok_cnt 0 ans 0 for x in data: valid smin x smax if not fault: if valid: ans 1 err_cnt 0 else: err_cnt 1 if err_cnt N: fault True ok_cnt 0 else: if valid: ok_cnt 1 if ok_cnt N: fault False err_cnt 0 ok_cnt 0 ans 1 else: ok_cnt 0 print(ans) if __name__ __main__: solve()Python 有个写起来很爽但容易出错的地方smin x smax这种链式比较非常直观但别把方向写反成smin x and x smax之外的逻辑。另一个细节是tokens可能包含换行符号但split()默认全部按空白切分所以任何多余空格和换行都不需要担心。3.3 Java 版本Java 在机试里主要用 Scanner 或者 BufferedReader 读取。数据量 100000 时 Scanner 完全够用但代码里我建议显式处理 nextInt 的顺序避免读漏。Java 的 long 对应答案累加int 存数据本身没问题。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int smin sc.nextInt(); int smax sc.nextInt(); int N sc.nextInt(); int M sc.nextInt(); int[] data new int[M]; for (int i 0; i M; i) { data[i] sc.nextInt(); } sc.close(); boolean fault false; int errCnt 0; int okCnt 0; long ans 0; for (int x : data) { boolean valid (x smin x smax); if (!fault) { if (valid) { ans; errCnt 0; } else { errCnt; if (errCnt N) { fault true; okCnt 0; } } } else { if (valid) { okCnt; if (okCnt N) { fault false; errCnt 0; okCnt 0; ans; } } else { okCnt 0; } } } System.out.println(ans); } }Java 需要注意的坑是sc.nextInt()自动跳过空白字符所以即使输入里有多余空格也不影响。但如果在某些在线平台卡输入性能Scanner 可能会拖后腿100000 的数据量还远没到瓶颈。真正容易出问题的反而是类型不匹配比如把 ans 定义成 int极端情况下会溢出成负数。3.4 JavaScript 版本JS 在华为OD机试里通常用 Node.js 环境输入方式是用 readline 逐行读取。这里有个常见的踩坑点readline 的回调里拿到的行可能带首尾空格一定要 trim如果数据行里有多个空格用split(/\s/)而不是split( )否则容易产生空字符串。function solve() { const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { const firstLine lines[0].split(/\s/).map(Number); const smin firstLine[0]; const smax firstLine[1]; const N firstLine[2]; const M Number(lines[1]); const data lines[2].split(/\s/).map(Number); let fault false; let errCnt 0; let okCnt 0; let ans 0; for (const x of data) { const valid x smin x smax; if (!fault) { if (valid) { ans; errCnt 0; } else { errCnt; if (errCnt N) { fault true; okCnt 0; } } } else { if (valid) { okCnt; if (okCnt N) { fault false; errCnt 0; okCnt 0; ans; } } else { okCnt 0; } } } console.log(ans); }); } solve();JS 的数值类型是双精度浮点当数据值超过 Number.MAX_SAFE_INTEGER 时会丢失精度但本题数据范围控制在 32 位整数内完全不用考虑。另一个细节是lines数组长度如果输入最后有多余空行第三行数据可能取错位置通常题目输入里不会有多余空行如果本地测试发现data是 undefined优先检查 split 正则。3.5 Go 版本Go 写算法题的风格比较固定fmt.Scan 简单直接但要保证输入顺序和类型完全匹配。fmt.Scan 会自动处理空白符对读入体验比较友好。ans 用 int 在大多数平台是 64 位但如果考试环境编译器的 int 是 32 位建议显式用 int64。package main import ( bufio fmt os ) func main() { var smin, smax, N int fmt.Scan(smin, smax, N) var M int fmt.Scan(M) data : make([]int, M) for i : 0; i M; i { fmt.Scan(data[i]) } fault : false errCnt : 0 okCnt : 0 ans : int64(0) for _, x : range data { valid : x smin x smax if !fault { if valid { ans errCnt 0 } else { errCnt if errCnt N { fault true okCnt 0 } } } else { if valid { okCnt if okCnt N { fault false errCnt 0 okCnt 0 ans } } else { okCnt 0 } } } fmt.Println(ans) }Go 版本里我额外引入了 bufio 和 os但其实这段代码根本没用到 bufio 的 Reader。如果只用 fmt.Scanimport 里删掉 bufio 和 os 即可。写成上面这样是为了方便你切换到fmt.Fscan或者bufio.NewScanner做高性能输入时直接改。机试里 100000 个数据用 fmt.Scan 完全够但一旦数据量变成百万级还是用 bufio 更稳。3.6 多语言实现横向对比语言输入解析方式遍历方式整数溢出注意点典型坑Ccin / scanf范围for或下标用 long long 存 ans忘记关同步导致输入慢Pythonsys.stdin.read().split()直接 for x in dataPython int 无溢出链式比较写反方向JavaScanner.nextInt()foreach 数组用 long 存 ans把 ans 定义成 intJavaScriptreadline 逐行读取for...of 数组超出安全整数范围会丢精度split 后出现空字符串Gofmt.Scanrange 切片用 int64 存 ansimport 引入未使用的包五种语言的算法逻辑完全一致差异全在输入输出和类型处理上。我个人的建议是刷题阶段至少用两种语言写一遍一种是自己最熟的一种是平时不太熟的。这个题的多语言版特别适合练手因为逻辑不复杂但能把读取、遍历、类型、输出这一套基本功全部覆盖到。4. 边界用例与机试避坑4.1 必测边界样例我把实际测试中能定位问题的几个用例整理成了表格建议提交前逐个跑一遍。样例输入输出验证点1 3 1 / 3 / 2 9 12N1单个越界立即触发故障1 3 2 / 4 / 1 9 2 32故障恢复瞬间第2个有效数据计入后结束1 3 2 / 6 / 9 8 7 2 3 41全部越界后恢复两个有效未达N计数为01 3 3 / 3 / 1 2 33全部有效无故障ans 等于 M5 10 2 / 5 / 4 11 4 11 60交替越界虽然越界次数多但从不连续不触发故障5 10 2 / 8 / 6 4 4 7 8 9 9 93故障期间出现正常数据但未恢复后续越界清空 okCnt这些用例覆盖了正常态与故障态的交叉边界。特别是最后一个用例故障后出现 7 8 9连续有效已经达到 3 个如果 N2那么在 8 的位置就会恢复并计入 8 和 9答案就是 3 个有效6、8、9你可以在本地动手验一遍确保代码行为和预期一致。4.2 最容易踩的五个坑第一个坑正常状态下遇到有效数据没有重置 errCnt。这个是错误率最高的很多人只记得 ans 加一忘了把连续越界计数归零。如果不重置一段有效-越界-有效-越界的序列会被误判为连续越界到达 N凭空触发故障。第二个坑恢复瞬间的第 N 个有效数据是否计入。我采用的约定是计入。但部分题目版本可能要求从恢复后的下一个数据开始计数这时候只需要把ans从if (okCnt N)内部移到下一次进入正常状态的代码分支也就是改成if (okCnt N) { fault false; errCnt 0; okCnt 0; // 本次数据作为恢复信号不计入 } // 下次遇到有效数据时正常 ans read刷题前务必确认自己面对的题目版本是哪一种否则会和标准答案差 1。第三个坑答案类型用 int 导致溢出。M 最大 100000如果每个数据都有效ans 最大也就是 100000int 其实够用。但有些题目为了加大难度会扩大数据规模或者把 Smin、Smax 设成很大导致 you 中间计算有溢出风险。用 long long 或者 int64 是零成本的保险没必要省。第四个坑JS 的split( )遇到多个连续空格会引入空字符串导致Number()变成 0直接把数据读错。统一用split(/\s/)是最稳妥的。Python 的split()默认处理所有空白反而没有这个问题。第五个坑故障状态下遇到越界数据忘了重置 okCnt。这个错误非常隐蔽。假如故障后连续有两个有效数据再遇到一个越界有些人会想越界这个本身不算有效但前面两个有效计数还在然后继续累加第三个有效就恢复。这是错的规则要求连续有效中间出现越界就断开了okCnt 必须清零重新计数。4.3 双机位考试环境下的实战建议华为OD机试的双机位指的是考试监控有两路摄像头一个拍正面一个拍侧面环境全程有人工抽查。这个条件下切屏、查资料、手机搜题都属于高风险操作基本等同于放弃本次考试。所以平时刷题就要练成编辑器里直接写完整代码的能力而不是依赖本地 IDE 的补全和在线搜索。另外机考是 ACM 模式题目只给输入输出规格所有代码要自己处理读取和打印。很多人习惯在力扣那种核心代码模式里填函数突然切换到自己写输入解析时会慌。建议在刷这个题的时候刻意用从 stdin 读、往 stdout 写的方式多训练几次C 的 cin/cout、Python 的 sys.stdin.read、JS 的 readline、Java 的 Scanner、Go 的 fmt.Scan 都要能无障碍写出。时间分配上这种模拟题一般 20 分钟内要搞定。如果 10 分钟还没理清状态转移立刻停下来在纸上画两个状态的转移图比盯屏幕硬想要高效得多。我个人在实际操作中的体会是这类题真正拉开差距的环节不在算法思考而在把规则翻译成代码时的严谨程度。采样过滤这道题给了我一个很深的教训——任何带连续二字的约束一定对应一个独立的计数器而且这个计数器必然在某些操作下需要清零。写之前花两分钟把计数器清零的条件想清楚写完之后逐行对着状态转移表检查基本可以一次通过。最后再分享一个小技巧调试状态机题目时不要只盯着最终输出对不对可以把 fault、errCnt、okCnt 三个变量在每次数据变化后打印出来肉眼对比每个节点的状态。这种方式定位问题比打断点还要快尤其在本地跑例子的时候一行printf就能把逻辑漏洞暴露得清清楚楚。