洛谷P15799找数题解析：从边界条件到C++实现，掌握找数类题目的通法

洛谷P15799这道叫找数的题标题短得让人放松警惕实际交上去却能用最简单的方式教会你什么叫边界条件。我刷题的时候见过不少人在这种题上反复WA——不是不会遍历而是把找这个词理解得太模糊到底找第一个还是找最小还是找所有题目里差一个词代码上差一整段逻辑。这篇文章就专门拆解找数这一类题从审题时怎么识别考点到暴力枚举为什么反而是最优解再到条件判断函数的写法、常见WA陷阱最后给出可以直接提交的C参考实现和同类题练习路线。无论你是刚准备CSP-J/GESP二级的入门选手还是刷题只求AC、经常被简单题罚时的老手按这条链路走一遍这类题基本就能闭眼写了。1. 看到找数别急着写循环先做这层拆题功夫1.1 找数题的本质数据来源、条件判断、输出策略三要素在洛谷上找数这类题最迷惑人的地方就是名字。听起来好像只要会写for循环就能做但实际上每一发WA都能追溯到三要素中的某一个没理顺。第一个要素是数据来源。题目给你一串数可能是直接放在数组里的也可能是一个范围内的自然数还可能来自某个需要自己生成的序列比如斐波那契数列。P15799这种入门定位的题目绝大多数情况是给你一个长度为n的数组。但你要养成一个条件反射先搞清楚数从哪来、以什么格式读入再动手写代码。数据来源判断错了后面全是白写。第二个要素是条件判断。你要找的不是任意一个数而是满足某个明确条件的数。能被3整除大于等于某个阈值各位数字之和等于10是回文数这些都算条件。条件写得不完整或者漏了隐含边界程序就会给出错误答案。我见过有人把大于10写成大于等于10两个字之差一组数据就挂了。第三个要素是输出策略。这决定了你在循环里做什么是找到第一个就停下来还是把所有满足条件的数都收集起来又或者要在遍历过程中维护一个最优值。输出策略和条件判断一样重要是WA的高发区。用一个生活化的类比来理解找数就像在一筐乒乓球里找带标记的球。你得先知道标记长什么样条件再决定是拿到第一个标记球就交卷还是把所有标记球都挑出来又或者只需要回答筐里到底有没有输出策略。球筐是什么、标记怎么定义、怎么交卷三个问题缺一不可。P15799我刷到时的题面属于比较直接的找第一个满足条件的数类型。为了让你能把这套思路迁移到所有找数题上我先把这类题的通法讲透再落到代码。1.2 四种常见题面问法对应的处理策略根据我刷题的经验找数题最常见的问法可以归纳成四种处理方式完全不同题面常见问法实质性要求循环内的处理方式找到第一个满足条件的数并输出输出第一个命中项命中后立即 break 或标记 found输出所有满足条件的数收集全部命中项遍历完整个数组逐个输出或用容器收集找出满足条件的最大/最小/第K小的数输出最优解的数值或下标每次命中后和当前最优值比较并更新判断是否存在满足条件的数只回答是/否设一个布尔标记命中后可以提前结束这里我想多说一个细节有些找数题要求输出的是下标不是数值。题面写输出满足条件的数的编号和输出满足条件的数代码里完全是两回事。我自己的习惯是拿到题面先拿笔圈出输出后面的内容确认它要的是数值、下标、个数还是别的然后再去写循环。这道工序花不了10秒钟却能避免大量无效提交。对于P15799我按最通用的找第一个满足条件的数并输出它的值不存在则输出-1来讲解。如果你的题面问法不同直接对照上面的表格调整循环逻辑即可。2. 从暴力枚举开始这类题的正解往往就是模拟本身2.1 为什么不要一上来就想花哨算法很多刚接触竞赛的读者有个误区觉得题解里出现二分、双指针、前缀和才算有水平。这是被高级算法毒害的典型症状。实际上竞赛里最重要的一项能力不是掌握多少高级算法而是准确地判断这道题需不需要高级算法。判断依据只有一个数据规模。P15799这种定位在入门/普及-边缘的题目n的量级通常不会超过10^5。对10^5个数做一次单向遍历在C里连0.01秒都用不到。这时候你还花半小时去思考一个更优雅的排序加二分方案纯属用大炮打蚊子还容易打偏。我可以把这个原则说得更直白算法选型的核心是先看数据范围跑不跑得动而不是先看题目像不像某类经典题。能跑得动的做法就是好做法。有人可能会说万一这题n是10^9呢——那题目就不会叫找数这么朴实的名字了数据范围也会在题面里明确写出来。竞赛题有一个惯例当题目需要你用高性能算法时数据范围一定会大得让你一眼就感觉到威胁反过来数据范围很温和时暴力模拟就是出题人希望的正解。2.2 以找第一个能被7整除的数为例的完整思考链路为了不悬在空中讨论我设定一个具体的示例题面这也是洛谷找数题最常见的形式给定 n 个整数请找出第一个能被 7 整除的数并输出。如果不存在输出 -1。拿到这个题面我的思考链路分四步读入n再读入n个整数存进数组a。从第1个数开始依次检查每个a[i]是否满足能被7整除。一旦满足立即输出a[i]并结束程序或退出循环。如果整个循环走完都没有命中说明不存在输出-1。这里最关键的思维落在第3和第4步你要对找到了和没找到两条路径都有明确安排。很多新手只写了找到了怎么输出完全忘了没找到输出-1的分支。结果数据里一旦有不满足的情况程序就什么都不输出评测机直接给一个WA你还一脸茫然找不到原因。用伪代码写出来就是这样读入 n 读入数组 a for i 0 to n-1: if a[i] 能被 7 整除: 输出 a[i] 结束程序 输出 -1 // 循环结束都没找到举个例子来手动模拟。假设输入6 12 14 21 28 35 7从头遍历12不是14不是21是停下来输出21。注意21是数组中第3个元素如果你错误地把第一个满足条件理解成最小的满足条件的数就会输出7那就错了。这种手动模拟一组样例的方法我强烈推荐给初学者——你模拟一遍等于自己当了一次评测机很多隐藏问题在动笔写代码之前就能暴露出来。2.3 复杂度分析O(n) 时间意味着什么这个思路的时间复杂度是O(n)空间上如果用数组存储就是O(n)如果采用一边读入一边判断的写法额外空间可以降到O(1)。对1e5以内的n来说运行时间秒出结果没有任何性能压力。这里顺带讲一个实用技巧。既然要找的是第一个满足条件的数而且判断只依赖当前读入的这个数本身那你完全可以不存数组读一个判断一个int n, x; bool found false; cin n; for (int i 1; i n; i) { cin x; if (!found x % 7 0) { cout x endl; found true; } } if (!found) cout -1 endl;注意这里用了found标记而不是直接在命中的地方return。区别在于如果题目后面还有第二组测试数据多组输入直接return会把整个程序都结束掉导致后续数据无法处理。用found标记可以做到只输出第一个命中项但循环继续把整组数据读完。这个细节在处理多组数据时非常重要也是从入门写法向竞赛写法过渡的一个小门槛。3. 条件判断函数的设计check函数写得好不好直接决定能否复用3.1 用独立函数包装判断逻辑而不是堆在main里这是我很想重点强调的一环。很多入门选手写这种题习惯把条件判断直接塞进for循环里for (int i 0; i n; i) { if (a[i] % 7 0 a[i] 10) { // 输出... } }小代码量时这个写法没毛病但条件一复杂比如能被3或5整除但不能被7和11同时整除且各位数字之和大于10你再把这一长串塞进循环里不光看着乱调试时也没法单独验证条件写得对不对。我的习惯是单独抽一个check函数// 返回 x 是否满足题目要找的数的条件 bool check(int x) { return x % 7 0; }主逻辑就变成干净的遍历 判断 输出三段式for (int i 0; i n; i) { if (check(a[i])) { // 按输出策略处理 } }这个习惯有三个实际好处。第一可读性好。看程序的人一眼就能明白main里管流程check里管条件各司其职。第二可测试性好。你可以单独测试checkcheck(7)应该返回truecheck(8)应该返回false。一旦测试结果不满足预期马上就能定位到是条件写错了而不是遍历逻辑错了排查范围缩小一半。第三可迁移性好。换一道找数题只需要改check函数内部的条件外层遍历和输出逻辑几乎不用动。这就是模板的真正来源——不是背代码而是把结构组织得足够清晰让替换成本降到最低。还有一条代码规范上的忠告check函数内部不要附带输出不要修改全局变量它只负责回答这个数是不是我们想要的回答完就返回。输出、计数、记录下标这些事交给外层做主。把职责拆开bug会少很多。3.2 常见条件速查整除、区间、奇偶、数位结合洛谷入门题的高频考法我把找数题常见的条件判断列成一个速查表每个都配上代码。整除条件x % a 0这里有一个需要留心的点如果a为0取模运算会直接导致运行时错误RE。题目一般会保证除数不为0但写代码时心里要有这根弦尤其当你从数据里读入除数时记得做一次防护判断。区间条件l x x r大于还是大于等于小于还是小于等于——这几个字是竞赛题里最常见的捉弄方式。建议每次写完区间判断都回题面再核对一遍边界取等情况。奇偶条件x % 2 ! 0 // 奇数C对负数的取模规则我马上会细说简单一句话判断奇偶不要用 x % 2 1要用 x % 2 ! 0或者位运算 x 1。负数环境下这两种写法才是稳的。数位条件比如各位数字之和、是否包含某个数字int tmp x; while (tmp) { int digit tmp % 10; // 处理 digit tmp / 10; }注意如果x本身是0上面的while循环一次都不执行。你要想统计0这个数字的出现次数得先对tmp为0的情况做单独处理。我把这些常见条件汇总成一张表方便以后写题时快速查阅条件类型常见写法最容易踩的坑整除x % a 0a 为 0 会 RE区间l x x r边界是否取等奇偶x % 2 ! 0负数下 x % 2 1 失效数位while (tmp) ...0 的情况需单独处理回文反转后与原数比较反转可能溢出大数据时3.3 负数参与判断时的一个隐藏坑这个细节在入门题里不常出现但一出就会让很多人莫名其妙WA。C的取模规则是余数的符号和被除数一致。举个例子-7 % 3 的结果是 -1不是 2。如果你拿它和0比较判断整除其实没有影响因为整除只看余数是不是0-7 % 3 -1 ! 0判断结果正确。真正有影响的是奇偶判断。如果你写 x % 2 1 来判断奇数当 x -3 时-3 % 2 -1不等于1于是你错误地把一个奇数判定成了不是奇数。正确的写法是 x % 2 ! 0或者更推荐用位运算 x 1——这个规则对负数同样成立因为补码的最低位就是奇偶标志位。做P15799这类题时测试数据大概率全是正整数但你不能保证某个隐藏数据点里没有负数。我个人给自己定的规矩是题面没说输入均为正整数时一律按可能有负数来处理。多写一个防弹的条件少吃一次罚时这笔买卖很划算。4. 完整代码实现与洛谷提交避坑记录4.1 一份可直接提交的参考实现C下面这份代码按找第一个能被7整除的数找不到输出-1来实现风格偏模板化方便以后迁移#include iostream using namespace std; // 判断 x 是否满足题目要找的数的条件 bool check(int x) { return x % 7 0; } int main() { int n; cin n; bool found false; int ans -1; for (int i 0; i n; i) { int x; cin x; if (!found check(x)) { ans x; found true; // 这里不 break保证整组数据读完 } } if (found) { cout ans endl; } else { cout -1 endl; } return 0; }如果你追求极致简洁也可以直接用 return 0 提前结束int main() { int n; cin n; for (int i 0; i n; i) { int x; cin x; if (x % 7 0) { cout x endl; return 0; } } cout -1 endl; return 0; }两种写法都能AC。前一种更接近可扩展模板后一种代码更短。我的建议是比赛时间紧张时用第二种平时练习用第一种把结构感练出来。4.2 从expected 和 read 能反推输入吗聊到评测反馈的正确用法我在准备这篇题解时看到有人在社区问洛谷上 expected 和 read 能反推输入吗这个问题背后是连续WA几发之后的焦躁我完全理解。评测系统给出的期望输出和实际输出确实能让猜测有一点点依据但想靠这一两个数字反推出完整输入效率极低。与其琢磨怎么反推测试数据不如自己动手构造用例。我总结了一套专治找数题的边界自测清单每次提交WA之后按顺序过一遍最小规模n1且这一个数恰好满足条件或者恰好不满足条件分别测一次。无解情况所有数都不满足条件确认程序输出了-1或其他兜底值。多个解数组里出现两个以上满足条件的数确认输出的是第一个而不是最后一个。负数和零如果题面没有排除混入几个负数和0确认奇偶、整除判断都没问题。较大规模n取到10^5级别确认程序不超时、不越界、不卡输入输出。你想想这五种用例都跑过了评测机还能拿什么来卡你呢大概率是没什么可卡的了。所以遇到WA第一步永远是构造样例而不是去解读expected和read。把调试精力花在可控的事情上才能最快靠近正确答案。4.3 我在写这道题时踩过的两个真实大坑第一个坑漏写无解分支。我第一次写找数题循环写对了条件写对了找到第一个命中项后输出也写对了唯独没有处理一直没找到怎么办。评测结果是WA而不是RE因为程序什么都没输出和期望输出完全对不上。那次罚时之后我给自己立了一个规矩写查找类题目的循环前先把循环结束后没找到就输出兜底值这行写出来再回头写循环体。去看看那些竞赛选手的代码几乎都有这个兜底分支这真不是巧合是每个人都交过学费。第二个坑把第一个满足条件理解成了值最小的数。有一道题题面写着找到第一个满足条件的数我一看第字想当然以为是找最小值于是用了min更新逻辑。没错又是WA。后来反复读题才发现第一个指的是数组顺序上的第一个不是数值大小上的第一。这两种第一经常被混淆。凡是拿不准的就在草稿纸上画一个数组手动模拟一遍输出过程答案立刻就清楚了。这两个坑合起来说明一个道理找数题常常不是因为算法难而WA而是因为对题面关键词的理解不到位而WA。第一个最小的所有是否存在——这些词每一个都必须落实到代码里对应的特定写法上。5. 从P15799延展出去找数题族的练习地图5.1 找数类题目的三个升级方向把P15799做会之后你会发现找数是一个可以成体系刷的题目家族。我从三个方向梳理它的升级路径方便你对号入座安排练习。方向一数据规模变大。n从10^3变成10^6甚至更大单纯的O(n)遍历可能在时间限制内跑不完。这时需要引入排序二分、桶/哈希计数、前缀和等技巧。但要记住这些高级工具是数据规模逼着你换思路时才用的不是为了展示技术含量。方向二条件变得更复杂。简单整除升级为素数判断、回文数判断、各位数字之和、二进制中1的个数等等。面对复杂条件你往往需要预处理比如先用筛法把素数筛好然后在check函数里通过查表O(1)判断。这正好呼应前面强调的check函数独立设计——条件变了你只需要替换check的内部实现主循环一行都不用动。方向三输出要求更高。从输出一个数变成输出下标、输出所有满足条件的数并排序、输出满足条件的数的个数。这种升级最考验逻辑精确度但本质上也只是在check之外多维护一个计数器、一个容器或者一个排序步骤。实际竞赛题经常是两三个方向叠加出现的。刷题时要有意识地给每道题归个类主要考的是数据规模、条件复杂度还是输出细节这样练习效率会高很多而不是做完一道丢一道。5.2 与GESP二级、CSP-J入门级考点的对应关系从不少人的搜索习惯能看出很多人刷洛谷是奔着考级和竞赛去的。P15799这种找数题对应的考点非常清晰循环结构、分支结构、数组的基本操作、基本输入输出。这些也正是GESP二级和CSP-J入门级考查的高频基础。我建议按这样的顺序来练先做纯遍历题输入n个数求最大值、最小值、总和、平均值。这类题帮我把for循环和数组操作练成肌肉记忆。再做条件筛选题从序列中挑选满足特定条件的数输出它们或者统计个数。找数题就落在这个层级。最后做变式综合题把筛选结果拿去排序、去重、计数、反查下标或者把条件从简单整除换成回文、质数这类需要专门实现判断函数的场景。每做完一道题回头问自己三个问题我用的时间复杂度是多少条件判断有没有抽成独立函数如果n再扩大100倍这个做法还跑得动吗这三个问题坚持追问下来找数这个类别的题基本就难不住你了。基础题最大的价值恰恰在于暴露你的代码习惯问题而不是考察你的知识面。5.3 给刷题者的收尾建议建立属于你自己的判断模板最后这段说点实在的刷题方法。我刷了这么多年题最值钱的不是某个题的AC记录而是我在AC过程中沉淀下来的代码片段。比如这个找数题的check函数套路、无解兜底分支、用found标记实现多组数据读入的写法。这些片段攒多了做题速度和稳定性都会有肉眼可见的提升。我的具体做法是遇到一道值得记的题就把它的核心代码结构存进本地一个按类别整理的文档比如查找排序计数字符串这样分。下次碰到相似题先翻自己的模板对照题面改条件和输出策略。这比从零开始写快得多而且这些模板都是自己踩坑踩出来的比网上抄来的更贴合自己的思维习惯。做完P15799我的模板库里多了一条查找第一个满足条件的数模板里明确区分找到即输出和全部遍历后判断是否存在两种写法。做算法题说到底就是把陌生套路变成肌肉记忆的过程。找数题就是最值得先练起来的那块肌肉。我在P15799上花的时间换来的是后续一堆找XX题都顺畅了很多——这种连锁反应刷题刷多了你自然会有体会。